Time Limit: 1000 MS Memory Limit: 32726 K


Description

学校打算雇人升级教务系统,想确定每个月需要的程序猿的数量。现在已经拟定了详细的工程方案,确切地知道每个月至少需要多少名程序猿进行工作。当学校雇佣或解雇程序猿时,会有额外的费用。一旦程序猿被雇佣,即使他不工作,他也会得到薪水。学校知道雇用程序猿、解雇程序猿和程序猿工资的成本。然后将面临这样的问题:为了保持总成本最低,他每个月要雇用或解雇多少程序猿。

Input

第一行包含实例数T,即有多少组输入数据。
接着是T例,每例3行。第一行包含计划使用的项目的月份,不超过12个月。第二行包含雇用程序猿的成本、工资数额、解雇程序猿的成本。第三行包含几个数字,它们表示每个月需要的工人的最小数量。

Output

输出包含一行,所需要最小总成本。

Sample Input

1
3
4 5 6
10 9 11

Sample Output

199