Description

.一个工程部经理想每个月都确定员工的总人数。他知道每个月员工人数的最小值。当他雇用或解雇一个员工时，将有一笔额外的开销。一次，一个员工被解雇了，他将得到这个月的薪水即便他没有工作。经理知道解雇工人和雇用工人的开销，以及工人的薪水。因此，这个经理面临这样一个问题：他每个月将雇用或解雇多少员工才能使工程部的总开销最低。

Input

.输入数据可以包含若干数据集。每个数据集包含3行。第一行输入这个工程计划的工期(以月为单位)，不超过12个月。第二行包含雇用一个工人的开销，薪水总额，和解雇工人的开销。第三行包括多个数据，表示每个月需要的最小的工人数。在最后一行输入0表示结束。

Output

结果只有一行为这个项目的最小总花费。

Sample Input

3
4 5 6
10 9 11
0

Sample Output

199



能编写出来吗?
谢谢了~~