消除游戏

题目背景

在育华学校组织的编程实践活动里，有一款有趣的消除游戏场景。同学们需要处理一排信号球的消除规则，计算全部消除时能获得的最大能量，以此锻炼动态规划算法的应用能力，理解如何在不同消除策略中寻找最优解。

题目描述

在育华学校的消除游戏中，初始会获得 n 个排成一行的信号球，每个信号球有对应的颜色。

每次操作，可以选择消除：

• 相邻1个颜色相同的信号球，获得 a 能量值
• 相邻2个颜色相同的信号球，获得 b 能量值
• 相邻3个颜色相同的信号球，获得 c 能量值

信号球消除后，其两边的信号球会连在一起。目标是求出将所有信号球消除时，最多可以获得多少能量。

输入格式

第一行输入 4 个整数 n, a, b, c，分别表示信号球的数量、一消/二消/三消时可获得的对应能量值。
第二行输入 n 个整数 s₁~sₙ，第 i 个整数表示第 i 个信号球的颜色。

输出格式

输出全部消除信号球时最多可以获得的能量值。

样例

样例输入 1

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

样例输出 1

14  

数据规模与测试点