题目描述

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

输入格式

共三行。第一行为月数$\red{N}$（不超过$\red{12}$）。第二行含雇佣一个工人的费用，一个工人的工资和解雇一个工人的费用（$\red{<101}$）。第三行含$\red{N}$个数，分别表示每月最少需要的工人数($\red{<1001}$)每个数据之间用空格相隔。

输出格式

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

样例

输入样例

3
4 5 6
10 9 11

输出样例

199