一位管理项目的经理想要确定每个月需要的工人，他当然知道每月所需的最少工人数。当他雇佣或解雇一个工人时，会有一些额外支出。一旦一个工人被雇佣，即使他不工作，他也将得到工资。这位经理知道雇佣一个工人的费用，解雇一个工人的费用和一个工人的工资。现他在考虑一个问题：如何在每个月雇佣或解雇工人,才能把项目的总费用控制在最低。

输入有三行。第一行为月数n（不超过12）。第二行含雇佣一个工人的费用a，一个工人的工资b和解雇一个工人的费用c（1≤a,b,c≤100）。第三行含n个数，分别表示每月最少需要的工人数ti（0≤ti≤1000）。每个数据之间有一个空格隔开。

输出仅一行，表示项目的最小总费用。

【数据范围】

对于所有测试点，保证：

1 ≤ n ≤ 12

1 ≤ a,b,c ≤ 100

0 ≤ ti ≤ 1000

dp