Рядом с большим домом профессора Pang живёт колония из $m$ муравьёв, обитающая под землёй в пещере с $n$ отверстиями. Они выходят через отверстия за едой. Где же еда? Она должна быть в большом холодильнике профессора Pang. Муравьи хотят украсть еду из этого холодильника.

А именно, муравью нужна 1 секунда, чтобы выйти из пещеры через любое отверстие, и 1 секунда, чтобы войти через любое отверстие. Отверстия расположены в разных местах. Расстояние между $i$-м отверстием и холодильником равно $a_i$. Поэтому после выхода через $i$-е отверстие муравью требуется $a_i$ секунд, чтобы дойти до холодильника. После кражи еды ему требуется $a_i$ секунд, чтобы вернуться к $i$-му отверстию. Сама кража не занимает времени, поскольку муравьи достаточно искусны.

Каждый муравей выйдет из пещеры, украдёт что-нибудь из холодильника, а затем вернётся в пещеру и войдёт в неё. Каждый должен выйти ровно один раз, а затем вернуться. Муравей может произвольно выбрать отверстие для выхода и отверстие для входа; они не обязаны совпадать. Через любое отверстие в течение любой секунды может проходить не более одного муравья, выходящего из пещеры или входящего в неё. Нельзя, чтобы за одну и ту же секунду один муравей выходил, а другой входил через то же отверстие. Из-за этого ограничения пропускной способности некоторые муравьи могут быть вынуждены ждать перед выходом через отверстие и/или перед возвращением к отверстию после кражи.

Поэтому вам, хорошему другу профессора Pang, нужно вычислить минимальные затраты времени для достижения цели муравьями и подшутить над профессором, чтобы муравьи украли еду и не попались ему. Затраты времени определяются как суммарная длительность времени, в течение которого хотя бы один муравей находится не в пещере. Когда муравей входит или выходит через отверстие, он находится не в пещере.

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

Первая строка содержит одно целое число $T$ ($1\le T\le10^5$), обозначающее количество наборов входных данных.

Для каждого набора первая строка содержит два целых числа $n,m$ ($1\le n\le10^5$, $1\le m\le10^{14}$), обозначающих количество отверстий и количество муравьёв соответственно. Вторая строка содержит $n$ целых чисел $a_1,a_2,\ldots,a_n$ ($1\le a_i\le10^9$), обозначающих время, необходимое для пути от $i$-го отверстия до холодильника.

Гарантируется, что сумма $n$ по всем наборам не превышает $5\times10^5$.

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

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

Примеры

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

3
2 4
1 2
3 10
1 2 3
5 1
1 2 3 4 5

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

6
9
4

Примечание

В третьем наборе муравью нужно в сумме 2 секунды, чтобы выйти из пещеры и войти в неё через первое отверстие. Ещё 2 секунды нужны, чтобы дойти до холодильника и вернуться к отверстию.