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

Обратите внимание на необычно маленькое ограничение по времени (time limit).

Вам задана последовательность $$$a$$$ длины $$$n$$$, а также целое число $$$k$$$.

Сначала вы можете переставить элементы $$$a$$$ произвольным образом. После этого функция $$$f(a)$$$ определяется следующим образом:

  • Пусть $$$b$$$ — массив длины $$$k$$$, изначально полностью заполненный нулями.
  • Для каждого $$$1 \le i \le n$$$ по порядку прибавьте $$$a_i$$$ к любому из минимальных элементов массива $$$b$$$.
  • В конце этого процесса $$$f(a) = \max(b)$$$.

Найдите максимально возможное значение $$$f(a)$$$ среди всех перестановок массива $$$a$$$.

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 18$$$).

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

Гарантируется, что сумма значений $$$2^n$$$ по всем наборам входных данных не превосходит $$$2^{18}$$$.

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

Для каждого набора входных данных выведите одно целое число — максимально возможное значение $$$f(a)$$$ среди всех перестановок массива $$$a$$$.

Примеры
Входные данные
1
18 5
837492015 264819073 519603847 902746518 173058264 648291507 395174620 781532946 506847193 924613708 158397042 673029415 240785631 819456270 461302987 730619824 528947163 894271056
Выходные данные
2823249283
Входные данные
6
4 2
1 2 4 5
1 1
10
8 3
3 4 1 3 2 4 5 3
3 1
1000000000 1000000000 1000000000
17 6
6 7 67 4 1 41 6 9 69 3 1 4 1 5 9 2 6
2 2
1 2
Выходные данные
8
10
11
3000000000
85
2
Примечание

В первом наборе входных данных второго примера одной из оптимальных перестановок массива $$$a$$$ является $$$[1, 4, 2, 5]$$$. Значение $$$f(a)$$$ вычисляется следующим образом:

$$$i$$$$$$a_i$$$$$$b$$$
$$$-$$$$$$-$$$$$$[0, 0]$$$
$$$1$$$$$$1$$$$$$[1, 0]$$$
$$$2$$$$$$4$$$$$$[1, 4]$$$
$$$3$$$$$$2$$$$$$[3, 4]$$$
$$$4$$$$$$5$$$$$$[8, 4]$$$

После этого $$$f(a) = \max([8,4]) = 8$$$. Можно показать, что максимально возможное значение $$$f(a)$$$ равно $$$8$$$.

В третьем наборе входных данных второго примера одной из оптимальных перестановок массива $$$a$$$ является $$$[3, 1, 2, 3, 5, 4, 3, 4]$$$.