题目描述

相信你一定玩过各种各样的消除游戏。

在这个消除游戏中，你初始会获得 n 个排成一行的信号球。每个信号球有颜色。

每次，你可以选择相邻的一个/两个/三个相邻且颜色相同的信号球进行消除（如果只消除一个，无论如何肯定是颜色相同的），分别得到 a/b/c 的能量值。

信号球在消除后，其两边的信号球会连在一起。

聪明的你能不能求出信号球全部消除时最多可以获得多少能量？

输入格式

第一行 4 个整数 n,a,b,c 。表示信号球的数量和一/二/三消除时可以获得的对应能量。

接下来一行 n 个整数，第 i 个整数 $s_i$ 表示第 i 个信号球的颜色为 $s_i$ 。

输出格式

输出最多可以获得多少能量。

输入输出样例 #1

输入 #1

8 1 3 7
3 1 3 1 3 2 2 3

输出 #1

14

说明/提示

对于100%的数据，保证$1 \le n,s_i \le 300$,$0 \le a,b,c \le 10000$。