Problem Statement

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.

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$.

Input

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

Output

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