Problem Statement

Takahashi is trying to decide his schedule for $N$ days. Initially, none of the days are holidays.

He can repeat either of the following operations any number of times:

• Choose an integer $i$ between $1$ and $N$, inclusive, and make day $i$ a holiday. This operation costs $A_i$.
• Choose an integer $i$ between $2$ and $N-1$, inclusive, such that both day $i-1$ and day $i+1$ are already holidays, and make day $i$ a holiday. This operation is free.

Find the minimum total cost required to create a consecutive block of $K$ or more holidays.

$T$ test cases are given; solve each of them.

Constraints

• $1 \leq T \leq 2 \times 10^5$
• $1 \leq K \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• All input values are integers.
• The sum of $N$ over all test cases is at most $2\times 10^5$.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Here, $\mathrm{case}_i$ denotes the input for the $i$-th test case. Each test case is given in the following format:

N K
A_1 A_2 \dots A_N

Output

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