{"raw_statement":[{"iden":"problem statement","content":"You are given integers $N$, $K$, and a length-$N$ sequence of non-negative integers $A = (A_1, A_2, \\dots, A_N)$.\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$.\nWe 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:\n\n*   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$.\n\nFind 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:\n\n*   $B_i \\leq A_i$ holds for all $i = 1, 2, \\dots, N$.\n*   $B$ is a monotonically non-decreasing sequence and is a \"good sequence.\"\n\nYou have $T$ test cases; solve each of them."},{"iden":"constraints","content":"*   $1 \\leq T \\leq 10^5$\n*   $2 \\leq K \\leq N \\leq 2 \\times 10^5$\n*   $0 \\leq A_i \\leq 10^{9}$\n*   $A_i \\leq A_{i+1}$ holds for all $i = 1, 2, \\dots, N - 1$.\n*   All input values are integers.\n*   The sum of $N$ over all test cases in one input is at most $2 \\times 10^5$."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$T$\n$\\mathrm{case}_1$\n$\\vdots$\n$\\mathrm{case}_T$\n\nEach case is given in the following format:\n\n$N$ $K$\n$A_1$ $A_2$ $\\dots$ $A_N$"},{"iden":"sample input 1","content":"4\n4 2\n0 1 2 3\n4 3\n0 1 2 3\n20 5\n1 2 3 3 4 5 6 7 7 8 9 9 11 13 14 16 16 17 18 19\n20 10\n36410986 135774405 160873759 200077345 386257217 408140905 426675713 448759426 470780343 572969565 653981029 693304642 741916215 764524315 768298046 811893935 840607643 847634785 856942510 883746061"},{"iden":"sample output 1","content":"6\n5\n185\n739\n\nIn 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:\n\n1.  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)$.\n2.  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)$.\n3.  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)$.\n4.  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)$.\n5.  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)$.\n6.  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)$.\n\nThus, taking $B = A$ achieves the maximum sum $0+1+2+3=6$.\nIn 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."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}