310464: CF1837F. Editorial for Two

F. Editorial for Twotime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Berland Intercollegiate Contest has just finished. Monocarp and Polycarp, as the jury, are going to conduct an editorial. Unfortunately, the time is limited, since they have to finish before the closing ceremony.

There were $n$ problems in the contest. The problems are numbered from $1$ to $n$. The editorial for the $i$-th problem takes $a_i$ minutes. Monocarp and Polycarp are going to conduct an editorial for exactly $k$ of the problems.

The editorial goes as follows. They have a full problemset of $n$ problems before them, in order. They remove $n - k$ problems without changing the order of the remaining $k$ problems. Then, Monocarp takes some prefix of these $k$ problems (possibly, an empty one or all problems). Polycarp takes the remaining suffix of them. After that, they go to different rooms and conduct editorials for their problems in parallel. So, the editorial takes as much time as the longer of these two does.

Please, help Monocarp and Polycarp to choose the problems and the split in such a way that the editorial finishes as early as possible. Print the duration of the editorial.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of each testcase contains two integers $n$ and $k$ ($1 \le k \le n \le 3 \cdot 10^5$) — the number of problems in the full problemset and the number of problems Monocarp and Polycarp are going to conduct an editorial for.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the time each editorial takes.

The sum of $n$ over all testcases doesn't exceed $3 \cdot 10^5$.

Output

For each testcase, print a single integer — the smallest amount of time the editorial takes, if Monocarp and Polycarp can choose which $k$ of $n$ problems to conduct an editorial for and how to split them among themselves.

ExampleInput

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

Output

2
6
5
21
18
1

题目大意：
伯兰德校际比赛刚刚结束，Monocarp和Polycarp作为裁判，将进行编辑工作。不幸的是，由于他们必须在闭幕式前完成，所以时间有限。比赛共有n个问题，编号从1到n。第i个问题的编辑需要a_i分钟。Monocarp和Polycarp将针对其中的确切k个问题进行编辑。

编辑过程如下。他们面前有一套完整的n个问题的题目集，并按顺序排列。他们删除n-k个问题，而不改变剩余k个问题的顺序。然后，Monocarp取这些k个问题的某个前缀（可能为空，或者全部问题），Polycarp取剩余的后缀。之后，他们分别去不同的房间，并为他们的问题进行编辑工作。因此，编辑所需的时间是两者中较长的一个。

请帮助Monocarp和Polycarp选择问题和分割方式，以便尽可能早地完成编辑工作。输出编辑的持续时间。

输入数据格式：
第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。
每个测试用例的第一行包含两个整数n和k（1≤k≤n≤3×10^5）——完整题目集中的问题数量和Monocarp和Polycarp将进行编辑的问题数量。
第二行包含n个整数a_1, a_2, …, a_n（1≤a_i≤10^9）——每个编辑所需的时间。
所有测试用例的n之和不超过3×10^5。

输出数据格式：
对于每个测试用例，打印一个整数——如果Monocarp和Polycarp可以选择进行编辑的n个问题中的k个问题，并决定如何在他们之间分配，则编辑所需的最少时间。题目大意： 伯兰德校际比赛刚刚结束，Monocarp和Polycarp作为裁判，将进行编辑工作。不幸的是，由于他们必须在闭幕式前完成，所以时间有限。比赛共有n个问题，编号从1到n。第i个问题的编辑需要a_i分钟。Monocarp和Polycarp将针对其中的确切k个问题进行编辑。 编辑过程如下。他们面前有一套完整的n个问题的题目集，并按顺序排列。他们删除n-k个问题，而不改变剩余k个问题的顺序。然后，Monocarp取这些k个问题的某个前缀（可能为空，或者全部问题），Polycarp取剩余的后缀。之后，他们分别去不同的房间，并为他们的问题进行编辑工作。因此，编辑所需的时间是两者中较长的一个。 请帮助Monocarp和Polycarp选择问题和分割方式，以便尽可能早地完成编辑工作。输出编辑的持续时间。 输入数据格式： 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。 每个测试用例的第一行包含两个整数n和k（1≤k≤n≤3×10^5）——完整题目集中的问题数量和Monocarp和Polycarp将进行编辑的问题数量。 第二行包含n个整数a_1, a_2, …, a_n（1≤a_i≤10^9）——每个编辑所需的时间。 所有测试用例的n之和不超过3×10^5。 输出数据格式： 对于每个测试用例，打印一个整数——如果Monocarp和Polycarp可以选择进行编辑的n个问题中的k个问题，并决定如何在他们之间分配，则编辑所需的最少时间。