AT_abc446_c [ABC446C] Omelette Restaurant

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.

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 $ T $ lines. The $ i $ -th line ( $ 1\leq i\leq T $ ) should contain the answer for the $ i $ -th test case.

### Sample Explanation 1 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 $ . ### 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.