问题描述

高桥君正在为 $N$ 天的日程安排犯愁。最初，所有日子都不是假日。

他可以重复执行以下两种操作中的任意一种，次数不限：

• 选择一个介于 $1$ 到 $N$ 之间的整数 $i$（包含 $1$ 和 $N$），将第 $i$ 天设为假日。此操作花费 $A_i$。
• 选择一个介于 $2$ 到 $N-1$ 之间的整数 $i$（包含 $2$ 和 $N-1$），使得第 $i-1$ 天和第 $i+1$ 天都已经是假日，然后将第 $i$ 天设为假日。此操作免费。

求创建连续 $K$ 天或更多假日所需的最小总花费。

给定 $T$ 个测试用例；请解决每个测试用例。

限制因素

• $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$ 。

输入

输入内容由标准输入法提供，格式如下

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

这里， $\mathrm{case}_i$ 表示 $i$ -th 测试用例的输入。每个测试用例的格式如下：

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

输出

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

3
5 2
3 1 4 1 5
6 4
24 3 22 39 4 29
15 7
220651272 302798780 874479994 657822311 613294668 479624013 241168404 610547619 762548286 256160531 823041612 951553052 226556081 649525901 153805947

2
29
1902064780

对于第一个测试用例，可以通过执行以下操作创建一个至少包含两个假期的连续区块：

• 使用第一种操作，将 $2$ 日设置为节假日。这需要花费 $1$ 。
• 使用第一种类型的操作将 $4$ 日设为假日。花费 $1$ 。
• 使用第二种类型的操作，将 $3$ 天定为假期。这是免费的。

这一系列操作的总费用为 $2$ 。我们不可能以小于 $2$ 的代价连续创建两个或两个以上的假日，因此输出 $2$ 。