小明在玩一个消除游戏。这个消除游戏有点特别。游戏中，你会得到 n 个一维排列的有各自颜色的砖块。 消除的时候，你有三种消除方案。你可以单消一个砖块，这样你可以得到 a 的得分；如果两个颜色一样的砖块在一起，你可以将这两个砖块一起消除获得 b 的得分；如果三个颜色一样的砖块在一期，你可以将这三个砖块一起消除获得 c 的得分。 消除后，被消除的砖块自动消失，被消除砖块的左右两端的砖块将在消除之后挨在一起。 小明想知道在最优策略下他能得到多少得分。

输入描述:

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

输出描述:

输出最高得分