AT_abc446_c [ABC446C] Omelette Restaurant

AtCoder レストランは開店してから $ N $ 日間営業しました。 開店してから $ i $ 日目 $ (1\leq i\leq N) $ には次の行動が行われました。 - $ i $ 日目の朝に、 $ A_i $ 個の卵を仕入れる。 - $ i $ 日目の昼に、 $ B_i $ 個の卵を使用する。このとき、卵は **在庫にある卵の中で仕入れた順に使用される** 。 - $ i $ 日目の夜に、仕入れてから $ D $ 日間以上経過した卵をすべて処分する。 なお、 $ 1 $ 日目の朝の前の時点で卵の在庫は無く、それぞれの日の昼に卵が足りなくなることはありませんでした。 $ N $ 日目の夜の行動の後で、レストランに何個の卵が残っているか求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ 個目のテストケースに対する答えを出力せよ。

### Sample Explanation 1 $ 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 $ 日目に仕入れた卵を処分した後の個数を出力することに注意してください。 ### 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 $ - $ N $ 日間のそれぞれの昼において、卵が足りなくなることはない。 - それぞれの入力において、各テストケースにおける $ N $ の総和は $ 2\times 10^5 $ 以下である。 - 入力はすべて整数