F. Разбор на двоих
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Только что закончилась Берлядская межвузовская олимпиада. Монокарп и Поликарп, как члены жюри, собираются провести разбор. К сожалению, время у них ограничено, так как надо закончить до церемонии закрытия.

В соревновании было $$$n$$$ задач. Задачи пронумерованы от $$$1$$$ до $$$n$$$. Разбор $$$i$$$-й задачи занимает $$$a_i$$$ минут. Монокарп и Поликарп планируют разобрать ровно $$$k$$$ из них.

Разбор проходит следующим образом. Перед ними лежит весь проблемсет из $$$n$$$ задач. Они убирают $$$n - k$$$ из них, не изменяя порядок оставшихся $$$k$$$ задач. Затем Монокарп забирает себе какой-то префикс из этих $$$k$$$ задач (возможно, пустой или все задачи). Поликарп забирает себе оставшийся суффикс. После этого они идут в разные комнаты и проводят разборы для своих задач параллельно. Так что разбор занимает столько времени, сколько занимает более долгий из этих двух.

Пожалуйста, помогите Монокарпу и Поликарпу выбрать задачи и разделить их между собой так, чтобы разбор закончился как можно раньше. Выведите длительность разбора.

Входные данные

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

В первой строке каждого набора входных данных записаны два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 3 \cdot 10^5$$$) — количество задач во всем проблемсете и количество задач, для которых Монокарп и Поликарп планируют провести разбор.

Во второй строке записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — время, которое занимает каждый разбор.

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.

Выходные данные

На каждый набор входных данных выведите одно целое число — наименьшее время, которое может занять разбор, если Монокарп и Поликарп могут выбирать, какие $$$k$$$ из $$$n$$$ задач разбирать и как разделять их между собой.

Пример
Входные данные
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
Выходные данные
2
6
5
21
18
1