小 C 要购买 � n 个物品，这些物品有前置关系，必须依次购买（即在购买了第 � i 个后才能购买第 � + 1 i+1 个）。

他初始有 � m 张优惠劵和无穷多个金币。每个物品有两个属性，价格 � � a i ​ 和优惠劵的使用上限 � � ( 0 ≤ � � ≤ � � ) b i ​ (0≤b i ​ ≤a i ​ )。

购买一个物品的流程如下：

选择使用 � ( 0 ≤ � ≤ � � ) x(0≤x≤b i ​ ) 张优惠券，付出 � � − � a i ​ −x 个金币和 � x 张优惠券。 购买完后可得到 ⌊ � � − � � ⌋ ⌊ c a i ​ −x ​ ⌋ 张优惠券（即一次购买中，每付出 � c 个金币可以得到一张优惠券， � c 为给定常数） 小 C 想求出最少花费多少个金币能购买全部物品。

输入格式 本题包含多组数据，第一行包含一个整数 � T，表示数据组数。

对于每组数据：

第一行包含三个整数 � , � , � n,m,c。 第二行包含 � n 个整数 � 1 , � 2 , . . . , � � a 1 ​ ,a 2 ​ ,...,a n ​ 表示每个物品的价格。 第三行包含 � n 个整数 � 1 , � 2 , . . . , � � b 1 ​ ,b 2 ​ ,...,b n ​ 表示优惠劵的使用上限。 输出格式 对于每组数据输出一行：

第一行输出一个整数，表示最少需要的金币数量。 输入输出样例 输入 #1复制 4 6 16 2 17 14 13 5 13 4 12 5 5 2 10 2 6 4 2 8 1 20 10 4 10 8 1 15 3 4 6 5 40 7 21 47 7 25 47 9 26 4 4 39 5 151 10 86 84 164 158 160 43 42 82 79 80 输出 #1复制 34 34 95 463 输入 #2复制 见附件 ex_shop2.in。 输出 #2复制 见附件 ex_shop2.out。 说明/提示 对于所有数据， 1 ≤ ∑ � ≤ 1 0 6 , 0 ≤ � , � � , � � ≤ 1 0 9 , 2 ≤ � ≤ 1 0 9 1≤∑n≤10 6 ,0≤m,a i ​ ,b i ​ ≤10 9 ,2≤c≤10 9 。

Subtask 1 (5 pts)： 1 ≤ � ≤ 5 , 1 ≤ � ≤ 10 , 1 ≤ � , ∑ � � , ∑ � � ≤ 10 1≤T≤5,1≤n≤10,1≤m,∑a i ​ ,∑b i ​ ≤10 Subtask 2 (10 pts)： � �

� � a i ​ =b i ​

Subtask 3 (10 pts)： 1 ≤ ∑ � ≤ 500 , 1 ≤ ∑ � , ∑ � � , ∑ � � ≤ 500 1≤∑n≤500,1≤∑m,∑a i ​ ,∑b i ​ ≤500 Subtask 4 (10 pts)： 1 ≤ ∑ � ≤ 6000 , 1 ≤ ∑ � , ∑ � � , ∑ � � ≤ 6000 1≤∑n≤6000,1≤∑m,∑a i ​ ,∑b i ​ ≤6000 Subtask 5 (10 pts)： 1 ≤ ∑ � ≤ 6000 1≤∑n≤6000 Subtask 6 (15 pts)： 1 ≤ ∑ � ≤ 2 × 1 0 5 , 2 ≤ � ≤ 20 1≤∑n≤2×10 5 ,2≤c≤20 Subtask 7 (10 pts)： 1 ≤ ∑ � ≤ 1 × 1 0 6 , 2 ≤ � ≤ 20 1≤∑n≤1×10 6 ,2≤c≤20 Subtask 8 (15 pts)： 1 ≤ ∑ � ≤ 2 × 1 0 5 1≤∑n≤2×10 5

Subtask 9 (15 pts)： 1 ≤ ∑ � ≤ 1 × 1 0 6 1≤∑n≤1×10 6

时间限制： 1s 1s

空间限制： 2048MB 2048MB