← 返回题目列表

AtCoder · abc446_c

E. 煎蛋餐厅

中文机器翻译题面 查看原题

分数: 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.