Поблизу великого будинку професора 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 секунди потрібно, щоб дістатися холодильника й повернутися до отвору.