题目描述

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

在这个消除游戏中，你初始会获得$n$个排成一行的信号球。每个信号球有颜色。 每次，你可以选择相邻的一个/两个/三个相邻且颜色相同的信号球进行消除（如果只消除一个，无论如何肯定是颜色相同的），分别得到$a$/$b$/$c$的能量值。

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

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

输入格式

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

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

输出格式

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

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

14

数据规模与约定

大样例

大样例下载