题目思路

题目和经典的区间dp非常相似，没有接触过区间dp的可以先了解一下概念。

设f[l][r]表示区间l到r范围内的砖块全部消除的最大分数，转移需要考虑所有可能的情况，这里考虑最后一种的消除方法，可以是最后剩下的1/2/3个相同元素消除。

一种经典的转移方法是枚举分成两半，即枚举中间点k，f[l][r]=max(f[l][k],f[k+1][r]),可以理解为分开消除区间[l,k]和[k+1,r]。这种经典的转移可以囊括不包含端点对在内的1/2/3元素消除。

端点l和端点r之间的相等的情况会是上述转移无法考虑到的，即最后留下l和r两块相同的砖消去，需要考虑f[l][r]=max(f[l][r],f[l+1][r-1]+max(a*2,b))，二者相同可以消一次*2也可以直接用消两次的代价。

题目描述

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

消除的时候，你有三种消除方案。你可以单一个砖块，这样你可以得到a的得分，如果两个颜色一样的砖块在一起，你可以将这两个砖块一起消除获得b的得分，如果三个颜色一样的砖块在一起，你可以将这三个砖块一起消除获得c的得分。消除后，被消除的砖块自动消失，被消除砖块的左右两端的砖块将在消除之后挨在一起小红想知道在最优策略下他能得到多少得分

输入描述

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

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

$1\le s_i \le n \le 300, 0\le a,b,c \le 10000$

输出描述

输出最高得分

样例

输入输出示例仅供调试，后台判题数据一般不包含示例

输入

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

输出

14