Editorial for Two
Contest: Educational Codeforces Round 149 (Rated for Div. 2)
Difficulty rating: 2400
Tags: binary search, data structures, greedy, implementation

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 format:
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 format:
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.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Example input:
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

Example output:
2
6
5
21
18
1

Editorial:
In the problem, we are asked to first choose $$$k$$$ problems, then fix a split into a prefix and a suffix. But nothing stops us from doing that in reverse. Let's fix the split of an entire problemset first, then choose some $$$l$$$ ($$$0 \le l \le k$$$) and $$$l$$$ problems to the left of the split and the remaining $$$k - l$$$ problems to the right of it.
That allows us to proceed with some polynomial solution already. Having fixed the split and $$$l$$$, we only have to find $$$l$$$ shortest editorials to the left and $$$k - l$$$ shortest editorials to the right. It's trivial to show that it's optimal.
That can be done in $$$O(n^2 \log n)$$$ easily or $$$O(n^2)$$$ if you think a bit more. That solution doesn't really help with the full one, so I won't elaborate.
Next, when we see something along the lines of "minimize the maximum", we think about binary search.
Let's try to apply it here. Binary search over the answer — now we want the sum of the left and the right parts of the split to be less than or equal to some fixed $$$x$$$.
More specifically, there should exist some $$$l$$$ that the sum of $$$l$$$ smallest elements to the left is $$$\le x$$$ and the sum of $$$k - l$$$ smallest elements to the right is $$$\le x$$$. Let's say it differently. There should be at least $$$l$$$ elements to the left with their sum being $$$\le x$$$, same to the right. And once more. The largest set with the sum $$$\le x$$$ to the left is of size at least $$$l$$$, same to the right.
But that doesn't really require that $$$l$$$ now, does it? Find the largest set with the sum $$$\le x$$$ to the left and to the right. The sum of their sizes should be at least $$$k$$$.
Let's calculate the size of this largest set for all prefixes and all suffixes of the array. Then we will be able to check the condition in $$$O(n)$$$.
You can precalculate the sizes for all prefixes in $$$O(n \log n)$$$. The idea is the following. Take the set for some prefix $$$i$$$. Add the $$$(i+1)$$$-st element to it. If its sum is $$$\le x$$$, then it's the new set. Otherwise, keep removing the largest element from it until the sum becomes $$$\le x$$$.
That solution is $$$O(n \log A \log n)$$$, where $$$A$$$ is the sum of the array, so you should be careful with the constant factor. For example, doing it with a multiset or with a segment tree probably won't pass. priority_queue is fast enough, though.
However, we can do it faster. Imagine a solution with the multiset. Let's replace it with a doubly-linked list.
In particular, we want the following operations:
• insert an element in it;
• check and remove the last element from it.
If we never removed any element, we would be able to determine where to insert each element. We can just precalculate that before the binary search in $$$O(n \log n)$$$. For each element, find the largest element less than or equal to it and to the left of it. That would be the previous element when this one is inserted.
When we remove elements, it can happen that this previous element was already removed when we attempt to insert this one. We can use the specificity of the problem to avoid that issue. Notice that if we removed an element less than or equal to the current one, then the current one could never be inside an optimal multiset. So we can just skip this element.
To implement such a list, we can renumerate all elements into values from $$$0$$$ to $$$n-1$$$ (in order of $$$(\mathit{value}, i)$$$). Then, for each $$$i$$$ store the value of the previous and the next elements existing in the list. For convenience, you can also add nodes $$$n$$$ and $$$n+1$$$, denoting the tail and the head of the list.
Then insert and remove is just rearranging some links to the previous and the next elements.
Overall complexity: $$$O(n \log A)$$$ per testcase, where $$$A$$$ is the sum of the array.