AT_abc456_f.Plan Holidays

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.

高桥正在规划 $N$ 天的日程安排。初始时，没有任何一天是假日。

他可以任意次重复以下两种操作之一：

• 选择一个整数 $i$（$1 \le i \le N$），将第 $i$ 天设为假日。该操作花费 $A_i$。
• 选择一个整数 $i$（$2 \le i \le N-1$），使得第 $i-1$ 天和第 $i+1$ 天均已是假日，并将第 $i$ 天设为假日。该操作免费。

求构造一段长度至少为 $K$ 的连续假日区间所需的最小总花费。

共给出 $T$ 组测试数据，请分别求解。

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$

输入从标准输入中按以下格式给出：

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

其中，$\mathrm{case}_i$ 表示第 $i$ 个测试用例的输入。每个测试用例按以下格式给出：

$N$ $K$
$A_1$ $A_2$ $\dots$ $A_N$

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

输出 $T$ 行。第 $i$ 行应包含第 $i$ 个测试用例的答案。

Sample 1 Explanation:
For the first test case, a consecutive block of at least two holidays can be created by performing operations as follows:

• Make day $2$ a holiday using the first type of operation. This costs $1$.
• Make day $4$ a holiday using the first type of operation. This costs $1$.
• Make day $3$ a holiday using the second type of operation. This is free.

The total cost of this sequence of operations is $2$. It is impossible to create a consecutive block of two or more holidays with a cost less than $2$, so output $2$.

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

样例 1 解释：
对于第一个测试用例，可通过如下操作构造一个长度至少为 2 的连续假日区间：

• 使用第一类操作将第 $2$ 天变为假日，花费为 $1$。
• 使用第一类操作将第 $4$ 天变为假日，花费为 $1$。
• 使用第二类操作将第 $3$ 天变为假日，该操作免费。

此操作序列的总花费为 $2$。无法以低于 $2$ 的花费构造出长度不少于 2 的连续假日区间，因此输出 $2$。

约束条件

• $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$
• 所有输入值均为整数。
• 所有测试用例的 $N$ 之和不超过 $2\times 10^5$。