【CZYZOI 2017.04.20 A】 credit

内存限制: 256 MiB 时间限制: 1000 ms
标准输入输出

题目描述

大M所在的怪兽大学共有 nn 项课程,每项课程都有一个学分 viv_i ,各门课程的学分都有同一个上限 maxvmaxv

在每年的毕业成绩结算中,一个怪兽的总成绩 total=minxcmin+cntmaxcmaxtotal=minx*cmin+cntmax*cmax

其中 minxminx 为这个怪兽 nn 门课程中学分最低课程的分数,cntmaxcntmax 为这个怪兽 nn 门课程中学分达到上限 maxvmaxv 的个数,cmincmincmaxcmax 为给出的常数。

现在学期已经过去大半,大M想要提高自己今年的总成绩。

距离学期结束还有 mm 天,每一天大M可以进修任意一门学分未满的课程并使该门课程的学分 +1+1(你也可以什么课都不上)。

请你帮帮大M,告诉他他最高可以获得的总成绩为多少。

输入格式

第一行 55 个整数分别为 n,maxv,cmax,cmin,mn,maxv,cmax,cmin,m

第二行 nn 个整数表示大M各门课程的初始学分。

输出格式

仅一行 11 个整数为大M最多能获得的总成绩。

样例

输入样例1

3 5 10 1 5
1 3 1

输出样例1

12

输入样例2

3 5 10 1 339
1 3 1

输出样例2

35

数据范围与提示

对于 100%100\% 的数据,

对于其中 10%10\% 的数据,cmax=0cmax=0

对于其中另外 10%10\% 的数据,cmin=0cmin=0