{"raw_statement":[{"iden":"statement","content":"小 C 要购买 $n$ 个物品，这些物品有前置关系，必须**依次**购买（即在购买了第 $i$ 个后才能购买第 $i+1$ 个）。\n\n他初始有 $m$ 张优惠劵和无穷多个金币。每个物品有两个属性，价格 $a_i$ 和优惠劵的使用上限 $b_i(0\\le b_i\\le a_i)$。\n\n购买一个物品的流程如下：\n\n- 选择使用 $x(0\\le x\\le b_i)$ 张优惠券，付出 $a_i-x$ 个金币和 $x$ 张优惠券。\n- 购买完后可得到 $\\lfloor \\frac{a_i-x}{c} \\rfloor$ 张优惠券（即一次购买中，每付出 $c$ 个金币可以得到一张优惠券，$c$ 为给定常数）\n\n小 C 想求出最少花费多少个金币能购买全部物品。"},{"iden":"input","content":"本题包含多组数据，第一行包含一个整数 $T$，表示数据组数。\n\n对于每组数据：\n\n- 第一行包含三个整数 $n,m,c$。\n- 第二行包含 $n$ 个整数 $a_1,a_2,...,a_n$ 表示每个物品的价格。\n- 第三行包含 $n$ 个整数 $b_1,b_2,...,b_n$ 表示优惠劵的使用上限。"},{"iden":"output","content":"对于每组数据输出一行：\n\n- 第一行输出一个整数，表示最少需要的金币数量。"},{"iden":"note","content":"对于所有数据，$1\\le \\sum n\\le 10^6,0\\le m,a_i,b_i\\le 10^9,2\\le c\\le 10^9$。\n\n- Subtask 1 (5 pts)：$1\\le T\\le 5,1\\le n\\le 10,1\\le m,\\sum a_i,\\sum b_i\\le 10$\n- Subtask 2 (10 pts)：$a_i=b_i$\n- Subtask 3 (10 pts)：$1\\le \\sum n\\le 500,1\\le \\sum m,\\sum a_i,\\sum b_i\\le 500$\n- Subtask 4 (10 pts)：$1\\le \\sum n\\le 6000,1\\le \\sum m,\\sum a_i,\\sum b_i\\le 6000$\n- Subtask 5 (10 pts)：$1\\le \\sum n\\le 6000$\n- Subtask 6 (15 pts)：$1\\le \\sum n\\le 2\\times 10^5,2\\le c\\le 20$\n- Subtask 7 (10 pts)：$1\\le \\sum n\\le 1\\times 10^6,2\\le c\\le 20$\n- Subtask 8 (15 pts)：$1\\le \\sum n\\le 2\\times 10^5$\n- Subtask 9 (15 pts)：$1\\le \\sum n\\le 1\\times 10^6$\n\n时间限制：$\\texttt{1s}$\n\n空间限制：$\\texttt{2048MB}$"}],"translated_statement":null,"sample_group":[["4\n6 16 2\n17 14 13 5 13 4\n12 5 5 2 10 2\n6 4 2\n8 1 20 10 4 10\n8 1 15 3 4 6\n5 40 7\n21 47 7 25 47 \n9 26 4 4 39 \n5 151 10\n86 84 164 158 160\n43 42 82 79 80","34\n34\n95\n463"],["见附件 ex_shop2.in。","见附件 ex_shop2.out。"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}