Description

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

Format

Input

输入文件包含三行。第一行为月数n（n≤12）；第二行含雇用一个工人的费用，一个工人的工资和解雇一个工人的费用（≤100）。第三行含n个数，分别表示每月最少需要的工人数（≤1000）。每个数据之间有一个空格隔开。

Output

输出仅一个数据，即表示项目的最小总费用。

Samples

3
4 5 6
10 9 11

199

Limitation

1s, 1024KiB for each test case.