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