AT_agc071_d [AGC071D] Level K Terms

You are given integers $ N $ , $ K $ , and a length- $ N $ sequence of non-negative integers $ A = (A_1, A_2, \dots, A_N) $ . $ A $ is a monotonically non-decreasing sequence. That is, $ A_i \leq A_{i+1} $ holds for all $ i = 1, 2, \dots, N - 1 $ . We call a length- $ N $ sequence of non-negative integers $ X = (X_1, X_2, \dots, X_N) $ a "good sequence" if $ X $ is monotonically non-decreasing and one can make all elements of $ X $ equal to $ 0 $ by applying the following operation zero or more times: - Choose an integer $ i $ such that $ 1 \leq i \leq N - K + 1 $ . Let $ S = X_i + X_{i+1} + \dots + X_{i+K-1} $ . Replace each of the $ i $ -th through $ (i+K-1) $ -th elements of $ X $ with $ \left\lfloor \frac{S}{K} \right\rfloor $ . Find the maximum possible value of $ \sum_{i=1}^N B_i $ for a sequence of non-negative integers $ B = (B_1, B_2, \dots, B_N) $ that satisfy all of the following conditions: - $ B_i \leq A_i $ holds for all $ i = 1, 2, \dots, N $ . - $ B $ is a monotonically non-decreasing sequence and is a "good sequence." You have $ T $ test cases; solve each of them.

The input is given from Standard Input in the following format: > $ T $ $ \mathrm{case}_1 $ $ \vdots $ $ \mathrm{case}_T $ Each case is given in the following format: > $ N $ $ K $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

Print $ T $ lines. The $ i $ -th line should contain the answer for the $ i $ -th test case.

### Sample Explanation 1 In the first test case, $ A $ itself is a "good sequence." For example, we can make all elements of $ A $ equal to $ 0 $ with the following steps: 1. Let $ i=3 $ . Then, $ S=A_3+A_4=5 $ . Replace $ A_3 $ and $ A_4 $ with $ \left\lfloor \frac{5}{2} \right\rfloor = 2 $ , resulting in $ A=(0,1,2,2) $ . 2. Let $ i=2 $ . Then, $ S=A_2+A_3=3 $ . Replace $ A_2 $ and $ A_3 $ with $ \left\lfloor \frac{3}{2} \right\rfloor = 1 $ , resulting in $ A=(0,1,1,2) $ . 3. Let $ i=3 $ . Then, $ S=A_3+A_4=3 $ . Replace $ A_3 $ and $ A_4 $ with $ \left\lfloor \frac{3}{2} \right\rfloor = 1 $ , resulting in $ A=(0,1,1,1) $ . 4. Let $ i=1 $ . Then, $ S=A_1+A_2=1 $ . Replace $ A_1 $ and $ A_2 $ with $ \left\lfloor \frac{1}{2} \right\rfloor = 0 $ , resulting in $ A=(0,0,1,1) $ . 5. Let $ i=2 $ . Then, $ S=A_2+A_3=1 $ . Replace $ A_2 $ and $ A_3 $ with $ \left\lfloor \frac{1}{2} \right\rfloor = 0 $ , resulting in $ A=(0,0,0,1) $ . 6. Let $ i=3 $ . Then, $ S=A_3+A_4=1 $ . Replace $ A_3 $ and $ A_4 $ with $ \left\lfloor \frac{1}{2} \right\rfloor = 0 $ , resulting in $ A=(0,0,0,0) $ . Thus, taking $ B = A $ achieves the maximum sum $ 0+1+2+3=6 $ . In the second test case, $ A $ is not a "good sequence." However, if we take $ B = (0,0,2,3) $ , then $ B $ is a "good sequence" and satisfies the conditions. ### Constraints - $ 1 \leq T \leq 10^5 $ - $ 2 \leq K \leq N \leq 2 \times 10^5 $ - $ 0 \leq A_i \leq 10^{9} $ - $ A_i \leq A_{i+1} $ holds for all $ i = 1, 2, \dots, N - 1 $ . - All input values are integers. - The sum of $ N $ over all test cases in one input is at most $ 2 \times 10^5 $ .