QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 2048 MB Total points: 100 Hackable ✓
Statistics

小 C 要购买 $ n $ 个物品,这些物品有前置关系,必须依次购买(即在购买了第 $ i $ 个后才能购买第 $ i+1 $ 个)。

他初始有 $ m $ 张优惠劵和无穷多个金币。每个物品有两个属性,价格 $ a_i $ 和优惠劵的使用上限 $ b_i(0\le b_i\le a_i) $。

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

  • 选择使用 $ x(0\le x\le b_i) $ 张优惠券,付出 $ a_i-x $ 个金币和 $ x $ 张优惠券。
  • 购买完后可得到 $ \lfloor \frac{a_i-x}{c} \rfloor $ 张优惠券(即一次购买中,每付出 $ c $ 个金币可以得到一张优惠券,$ c $ 为给定常数)

小 C 想求出最少花费多少个金币能购买全部物品。

输入格式

本题包含多组数据,第一行包含一个整数 $ T $,表示数据组数。

对于每组数据:

  • 第一行包含三个整数 $ n,m,c $。
  • 第二行包含 $ n $ 个整数 $ a_1,a_2,...,a_n $ 表示每个物品的价格。
  • 第三行包含 $ n $ 个整数 $ 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

见下发文件。

子任务

对于所有数据,$ 1\le \sum n\le 10^6,1\le m,a_i,b_i\le 10^9,2\le c\le 10^9 $。

$ \text{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 $

$ \text{Subtask 2 (10 pts)} $:$ a_i=b_i $

$ \text{Subtask 3 (10 pts)} $:$ 1\le \sum n\le 500,1\le \sum m,\sum a_i,\sum b_i\le 500 $

$ \text{Subtask 4 (10 pts)} $:$ 1\le \sum n\le 6000,1\le \sum m,\sum a_i,\sum b_i\le 6000 $

$ \text{Subtask 5 (10 pts)} $:$ 1\le \sum n\le 6000 $

$ \text{Subtask 6 (15 pts)} $:$ 1\le \sum n\le 2\times 10^5,2\le c\le 20 $

$ \text{Subtask 7 (10 pts)} $:$ 1\le \sum n\le 1\times 10^6,2\le c\le 20 $

$ \text{Subtask 8 (15 pts)} $:$ 1\le \sum n\le 2\times 10^5 $

$ \text{Subtask 9 (15 pts)} $:$ 1\le \sum n\le 1\times 10^6 $

时间限制:$ \text{1s} $

空间限制:$ \text{2048MB} $