分数: 300 点
问题陈述
AtCoder 餐厅开业 N 开封后天数。
当天 i (1\leq i\leq N)打开后,执行以下操作。
- 一天的早上 i, A_i 鸡蛋已购买。
- 当天中午 i, B_i 使用鸡蛋。在这里, 库存鸡蛋按照购买顺序使用.
- 白天晚上 i,所有已储存的鸡蛋 D 或更多天被丢弃。
当天上午之前没有鸡蛋库存 1,而且鸡蛋每天中午都不会用完。
查找当天晚上的行动后餐厅里还剩下多少鸡蛋 N.
T 给出了测试用例;逐一解决。
约束
- 1 \leq T\leq 2\times 10^5
- 1 \leq D \leq N \leq 2\times 10^5
- 1 \leq A_i,B_i \leq 10
- 任何一个中午鸡蛋都不会用完 N 天。
- 对于每个输入,总和 N 所有测试用例最多 2\times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
\mathrm{case}_i 代表 i- 第一个测试用例。
每个测试用例均按以下格式给出:
N D A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N
输出
输出 T 行。
的 i- 第行 (1\leq i\leq T)应包含以下问题的答案 i- 第一个测试用例。
示例输入 1
3 3 1 7 2 3 1 3 2 3 2 7 2 3 1 3 2 2 1 2 1 1 2
示例输出 1
3 5 0
在第一个测试用例中,执行以下操作。
- 最初,AtCoder Restaurant 没有鸡蛋。
- 一天的早上 1, 7 鸡蛋已购买。餐厅有 7 当天库存的鸡蛋 1.
- 当天中午 1, 1 使用鸡蛋。餐厅有 剩余 6 当天库存的鸡蛋 1 。
- 白天晚上 1,没有鸡蛋被丢弃。餐厅有 6 当天库存的鸡蛋 1 。
- 一天的早上 2, 2 鸡蛋已购买。餐厅有 6 当天库存的鸡蛋 1 和 2 当天库存的鸡蛋 2.
- 当天中午 2, 3 使用鸡蛋。餐厅有 3 当天库存的鸡蛋 1 和 2 当天库存的鸡蛋 2 。
- 白天晚上 2, 当天入库的鸡蛋 1 被丢弃。餐厅有 2 当天库存的鸡蛋 2 。
- 一天的早上 3, 3 鸡蛋已购买。餐厅有 2 当天库存的鸡蛋 2 和 3 当天库存的鸡蛋 3.
- 当天中午 3, 2 使用鸡蛋。餐厅有 3 当天库存的鸡蛋 3 。
- 白天晚上 3,没有鸡蛋被丢弃。 (这是因为所有鸡蛋都是当天库存的 2 已被使用。)餐厅已 3 当天库存的鸡蛋 3 。
因此, 3 白天晚上行动后,鸡蛋仍然存在 3,所以输出 3 在第一行。
对于第二个测试用例,记得输出丢弃当天存放的鸡蛋后的鸡蛋数量 1 在一天的晚上 3.