B. Сбор тортов
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Мэйпл хочет испечь несколько тортов для Чокола и Ванилы.

Однажды она обнаружила $$$n$$$ волшебных печей для тортов. $$$i$$$-я печь выпекает $$$a_i$$$ тортов каждую секунду. Торты остаются в своих печах до тех пор, пока их не соберут.

В конце каждой секунды она может телепортироваться к любой печи (включая ту, у которой она находится в данный момент) и собрать все торты, которые накопились в этой печи на тот момент.

Ваша задача — определить максимальное количество тортов, которое Мэйпл может собрать за $$$m$$$ секунд.

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n \leq 10^5$$$, $$$1\leq m\leq 10^8$$$) — количество волшебных печей и количество секунд, в течение которых Мэйпл будет собирать торты.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \le 10^5$$$) — количество тортов, которое $$$i$$$-я печь выпекает каждую секунду.

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

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

Для каждого набора входных данных выведите одно целое число, представляющее максимальное количество тортов, которое Мэйпл может собрать за $$$m$$$ секунд.

Пример
Входные данные
3
3 4
1 2 3
3 2
1 2 3
1 1000
100000
Выходные данные
20
8
100000000
Примечание

Для первого набора входных данных одно из оптимальных решений выглядит следующим образом:

  1. В конце первой секунды в печах содержится $$$1$$$, $$$2$$$ и $$$3$$$ торта соответственно. Мэйпл телепортируется к печи $$$3$$$ и собирает все $$$3$$$ торта. В печи $$$3$$$ теперь осталось $$$0$$$ тортов.
  2. В конце второй секунды в печах содержится $$$2$$$, $$$4$$$ и $$$3$$$ торта соответственно. Мэйпл телепортируется к печи $$$1$$$ и собирает $$$2$$$ торта. В печи $$$1$$$ теперь осталось $$$0$$$ тортов.
  3. В конце третьей секунды в печах содержится $$$1$$$, $$$6$$$ и $$$6$$$ тортов соответственно. Мэйпл телепортируется к печи $$$2$$$ и собирает все $$$6$$$ тортов. В печи $$$2$$$ теперь осталось $$$0$$$ тортов.
  4. В конце четвертой секунды в печах содержится $$$2$$$, $$$2$$$ и $$$9$$$ тортов соответственно. Мэйпл телепортируется к печи $$$3$$$ и собирает все $$$9$$$ тортов. В печи $$$3$$$ теперь осталось $$$0$$$ тортов.

В итоге Мэйпл собирает $$$3+2+6+9=20$$$ тортов.

Для второго набора входных данных одно из оптимальных решений выглядит следующим образом:

  1. В конце первой секунды в печах содержится $$$1$$$, $$$2$$$ и $$$3$$$ торта соответственно. Мэйпл телепортируется к печи $$$2$$$ и собирает все $$$2$$$ торта. В печи $$$2$$$ теперь осталось $$$0$$$ тортов.
  2. В конце второй секунды в печах содержится $$$2$$$, $$$2$$$ и $$$6$$$ тортов соответственно. Мэйпл телепортируется к печи $$$3$$$ и собирает все $$$6$$$ тортов. В печи $$$3$$$ теперь осталось $$$0$$$ тортов.

В итоге Мэйпл собирает $$$2+6=8$$$ тортов.