AT_abc456_f [ABC456F] Plan Holidays

Takahashi 正在为接下来的 $N$ 天制定日程安排。起初，没有任何一天是假期。 他可以无限次重复以下任一操作： - 选择一个整数 $i$，其中 $1 \leq i \leq N$，并将第 $i$ 天设为假期。该操作的花费为 $A_i$。 - 选择一个整数 $i$，其中 $2 \leq i \leq N-1$，且第 $i-1$ 天和第 $i+1$ 天都已经是假期，将第 $i$ 天设为假期。该操作免费。 请你计算，要创建一段长度至少为 $K$ 的连续假期区块，所需的最小总花费。 给定 $T$ 个测试用例；请依次求解每个用例。

输入从标准输入获取，格式如下： > $T$ > $\mathrm{case}_1$ > $\mathrm{case}_2$ > $\vdots$ > $\mathrm{case}_T$ 其中，$\mathrm{case}_i$ 表示第 $i$ 个测试用例的输入，具体格式如下： > $N\ K$ > $A_1\ A_2\ \dots\ A_N$

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

### 样例解释 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$。 由 ChatGPT 5 翻译