← 返回题目列表

Codeforces · 1842/I

I. 丹增和项链

中文机器翻译题面 查看原题

丹增有一条漂亮的项链。项链由 $$$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$$$。