← 返回题目列表

Codeforces · 1837/F

F. 两人社论

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

Berland 校际竞赛刚刚结束。 Monocarp 和 Polycarp 作为评审团将发表社论。不幸的是,时间有限,因为他们必须在闭幕式之前完成。

比赛中存在 $$$n$$$ 问题。问题的编号从 $$$1$$$ 到 $$$n$$$。第 $$$i$$$ 问题的社论需要 $$$a_i$$$ 分钟。 Monocarp 和 Polycarp 将针对 $$$k$$$ 的问题进行社论。

社论如下。他们面前有一整套按顺序排列的 $$$n$$$ 问题。他们消除了 $$$n - k$$$ 问题,而不改变剩余 $$$k$$$ 问题的顺序。然后,Monocarp 获取这些 $$$k$$$ 问题的一些前缀(可能是一个空问题或所有问题)。波利卡普 (Polycarp) 采用其中剩余的后缀。之后,他们去不同的房间,并行地针对自己的问题进行社论。因此,社论所花费的时间与两者中较长者所花费的时间一样多。

请帮助 Monocarp 和 Polycarp 选择问题和拆分,以便社论尽早完成。打印社论的持续时间。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 3 \cdot 10^5$$$) - 完整问题集中的问题数量以及 Monocarp 和 Polycarp 将进行编辑的问题数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) - 每个编辑所花费的时间。

所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 如果 Monocarp 和 Polycarp 可以选择针对 $$$n$$$ 问题中的 $$$k$$$ 问题进行编辑以及如何将它们分开,则编辑所需的最短时间。

示例

输入 #1

6
5 4
1 10 1 1 1
5 3
1 20 5 15 3
5 3
1 20 3 15 5
10 6
10 8 20 14 3 8 6 4 16 11
10 5
9 9 2 13 15 19 4 9 13 12
1 1
1

输出 #1

2
6
5
21
18
1