Не иллюзия обмана
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Четыре Всадника проникают в сейф, где хранятся драгоценности. В сейфе лежат $$$n$$$ слитков золота массами $$$a_1, a_2, ..., a_n$$$.

Из-за системы безопасности они не могут просто взять всё: при выходе сработает детектор, если количество оставшихся там слитков будет меньше количества слитков, вынесенных из сейфа.

Но Всадники не даром лучшие в своём деле, а потому решили перехитрить даже систему безопасности: находясь внутри сейфа, они могут взять любой слиток и разделить его на два новых слитка ненулевой целой массы, причём каждый из получившихся слитков можно затем поделить ещё таким же образом. В результате количество слитков в сейфе увеличится и они смогут вынести больше золота!

К сожалению, их проникновение уже засекли, и до того как их поймают, они успеют сделать не более $$$k$$$ разделений слитков. У Всадников очень мало времени, а золото упускать не хочется, поэтому им необходимо как можно скорее узнать, какое максимальное количество золота они смогут вынести из сейфа.

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

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

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_i$$$, где $$$i$$$-е число описывает величину массы $$$i$$$-го слитка из хранилища ($$$1 \le a_i \le 10^9$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите одно число — максимальную величину массы золота, которую Всадники смогут унести.

Примеры

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

    44 76 10 5 13 112 8 121 455 71 4 2 7 15

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

    1924426

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

    37 2481 145 877 391 359 141 6475 2794 251 19 838 6004 10012342284 102022008 124242424 173814882

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

    23962232412421594