C - Omelette Restaurant 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 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

1 個目のテストケースにおいて次の行動が行われます。

  • 最初、AtCoder レストランには卵がありません。
  • 1 日目の朝に卵を 7 個仕入れます。レストランには 1 日目に仕入れた卵が 7 個あります。
  • 1 日目の昼に卵を 1 個使用します。レストランには 1 日目に仕入れた卵が 6 個残っています。
  • 1 日目の夜に処分する卵はありません。レストランには 1 日目に仕入れた卵が 6 個残っています。
  • 2 日目の朝に卵を 2 個仕入れます。レストランには 1 日目に仕入れた卵が 6 個、2 日目に仕入れた卵が 2 個あります。
  • 2 日目の昼に卵を 3 個使用します。レストランには 1 日目に仕入れた卵が 3 個、2 日目に仕入れた卵が 2 個残っています。
  • 2 日目の夜に、1 日目に仕入れた卵を処分します。レストランには 2 日目に仕入れた卵が 2 個残っています。
  • 3 日目の朝に卵を 3 個仕入れます。レストランには 2 日目に仕入れた卵が 2 個、3 日目に仕入れた卵が 3 個あります。
  • 3 日目の昼に卵を 2 個使用します。レストランには 3 日目に仕入れた卵が 3 個残っています。
  • 3 日目の夜に処分する卵はありません。（2 日目に仕入れた卵は全て使用されているためです。）レストランには 3 日目に仕入れた卵が 3 個残っています。

よって、3 日目の夜の行動の後で、卵は 3 個残っているため、1 行目には 3 を出力します。

2 個目のテストケースにおいては、3 日目の夜に 1 日目に仕入れた卵を処分した後の個数を出力することに注意してください。

Score : 300 points

Problem Statement

AtCoder Restaurant was open for N days after opening.

On day i (1\leq i\leq N) after opening, the following actions were performed.

  • In the morning of day i, A_i eggs are purchased.
  • At noon on day i, B_i eggs are used. Here, eggs in stock are used in the order they were purchased.
  • In the evening of day i, all eggs that have been stocked for D or more days are discarded.

There were no eggs in stock before the morning of day 1, and eggs never ran out at noon on any day.

Find how many eggs remain in the restaurant after the evening action on day N.

T test cases are given; solve each.

Constraints

  • 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
  • Eggs never run out at noon on any of the N days.
  • For each input, the sum of N over all test cases is at most 2\times 10^5.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

\mathrm{case}_i represents the i-th test case.
Each test case is given in the following format:

N D
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N

Output

Output T lines.
The i-th line (1\leq i\leq T) should contain the answer for the i-th test case.

Sample Input 1

3
3 1
7 2 3
1 3 2
3 2
7 2 3
1 3 2
2 1
2 1
1 2

Sample Output 1

3
5
0

In the first test case, the following actions are performed.

  • Initially, AtCoder Restaurant has no eggs.
  • In the morning of day 1, 7 eggs are purchased. The restaurant has 7 eggs stocked on day 1.
  • At noon on day 1, 1 egg is used. The restaurant has 6 eggs stocked on day 1 remaining.
  • In the evening of day 1, no eggs are discarded. The restaurant has 6 eggs stocked on day 1 remaining.
  • In the morning of day 2, 2 eggs are purchased. The restaurant has 6 eggs stocked on day 1 and 2 eggs stocked on day 2.
  • At noon on day 2, 3 eggs are used. The restaurant has 3 eggs stocked on day 1 and 2 eggs stocked on day 2 remaining.
  • In the evening of day 2, the eggs stocked on day 1 are discarded. The restaurant has 2 eggs stocked on day 2 remaining.
  • In the morning of day 3, 3 eggs are purchased. The restaurant has 2 eggs stocked on day 2 and 3 eggs stocked on day 3.
  • At noon on day 3, 2 eggs are used. The restaurant has 3 eggs stocked on day 3 remaining.
  • In the evening of day 3, no eggs are discarded. (This is because all eggs stocked on day 2 have already been used.) The restaurant has 3 eggs stocked on day 3 remaining.

Thus, 3 eggs remain after the evening action on day 3, so output 3 on the first line.

For the second test case, remember to output the number of eggs after discarding the eggs stocked on day 1 in the evening of day 3.