丹增有一条漂亮的项链。项链由 $$$n$$$ 珍珠组成,编号从 $$$1$$$ 到 $$$n$$$,并用绳子连接珍珠 $$$i$$$ 和 $$$(i \text{ mod } n)+1$$$(对于所有 $$$1 \leq i \leq n$$$)。
有一天,Tenzing 想要通过切断一些绳子将项链切成几个部分。但对于项链的每个连接部分,不应有超过 $$$k$$$ 颗珍珠。剪断每根弦所需的时间可能不一样。丹增需要花费 $$$a_i$$$ 分钟切割珍珠 $$$i$$$ 和 $$$(i \text{ mod } n)+1$$$ 之间的绳子。
Tenzing 想知道切割项链的最短时间(以分钟为单位),以便每个连接部分不会有超过 $$$k$$$ 珍珠。
输入
每个测试包含多个测试用例。输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2\leq n\leq 5\cdot 10^5$$$, $$$1\leq k <n$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1\leq a_i\leq 10^9$$$)。
保证所有测试用例的$$$n$$$总和不超过$$$5 \cdot 10^5$$$。
输出
对于每个测试用例,输出所需的最短总时间(以分钟为单位)。
示例
输入 #1
4 5 2 1 1 1 1 1 5 2 1 2 3 4 5 6 3 4 2 5 1 3 3 10 3 2 5 6 5 2 1 7 9 7 2
输出 #1
3 7 5 15
注意
在第一个测试用例中,项链将被切割成$$$3$$$部分:$$$[1,2][3,4][5]$$$,因此总时间为$$$3$$$。
在第二个测试用例中,项链将被切割成$$$3$$$部分:$$$[5,1][2][3,4]$$$,Tenzing将切割连接$$$(1,2)、(2,3)$$$和$$$(4,5)$$$的绳子,所以总时间为$$$a_1+a_2+a_4=7$$$。