题目描述

小红在玩一个消除游戏。这个消除游戏有点特别，游戏中，你会得到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