小明在玩一个消除游戏。这个消除游戏有点特别。游戏中，你会得到n个一维排列的有各自颜色的砖块。

消除的时候，你有三种消除方案。你可以单消一个砖块，这样你可以得到a的得分；如果两个颜色一样的砖块在一起，你可以将这两个砖块一起消除获得b的得分；如果三个颜色一样的砖块在一起，你可以将这三个砖块一起消除获得c的得分。

消除后，被消除的砖块自动消失，被消除砖块的左右两端的砖块将在消除之后挨在一起。

小明想知道在最优策略下他能得到多少得分。

第一行4个整数n，a，b，c，表示砖块数量，和一消/二消/三消的得分。

接下来一行n个整数，第i个整数s_i表示第i个砖块的颜色。

1 ≤ si ≤ n ≤ 300，0 ≤ a, b, c ≤ 10000

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

14

先消除下标为2的3，获得1分，此时序列变为3113223

再消除两个连着的1，获得3分，序列变为33223

消除两个2，获得3分，序列变为333

消除3个3，获得7分。

总分为1+3+3+7=14

总时间限制：c/c++：1s；java/go: 3s；其他语言：9s