Description

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

Format

Input

第1行：1个整数n(n<=12)，表示月数。

第2行：3个用空格分开的整数h,s,f，分别表示雇佣一个工人的费用；一个工人的月工资和解雇一个工人的费用。

第3行：n个用空格分开的整数，分别表示每个月最少需要的工人数(每个月的工人数<=1000)

Output

第1行：1个整数，表示项目的最小总费用

Samples

3
4 5 6
10 9 11

199

Limitation

1s, 1024KiB for each test case.