B. Открытки с пожеланиями
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Говорят, что написание открыток с пожеланиями в канун Нового года может принести удачу. Вы написали открытки с пожеланиями и планируете подарить их Маленькой А.

Вы пригласили $$$n$$$ друзей, чтобы помочь вам доставить открытки с пожеланиями. Вы планируете дать $$$i$$$-му другу $$$b_i$$$ открыток с пожеланиями. Друзья будут посещать дом Маленькой А в порядке от $$$1$$$ до $$$n$$$, и каждый передаст ей все свои $$$b_i$$$ открытки с пожеланиями. Маленькая А всегда запоминает друга, который дарит ей больше всего открыток, поэтому после визита $$$j$$$-го друга она получает счастье, равное наибольшему количеству открыток, полученных до сих пор, то есть $$$\max(b_1, b_2, \ldots, b_j)$$$.

$$$i$$$-й друг может нести не более $$$a_i$$$ открыток, а общее количество открыток не может превышать $$$k$$$. Ваша задача — оптимально выбрать значения $$$b_i$$$, чтобы общее счастье Маленькой А после $$$n$$$ визитов было максимальным при этих ограничениях.

Обратите внимание, что некоторые друзья могут не нести ни одной открытки, Маленькая А не рассердится.

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le k \le 360$$$) — количество друзей и максимальное общее количество открыток.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \le a_i \le k$$$) — максимальное количество открыток, которое может нести каждый друг.

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

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

Для каждого набора входных данных выведите максимальное счастье, которое может получить Маленькая А.

Пример
Входные данные
4
3 4
0 0 1
6 8
1 2 0 5 1 8
3 4
1 0 4
5 8
2 4 5 4 3
Выходные данные
1
20
5
19
Примечание

В первом примере единственный способ распределить открытки с пожеланиями — это $$$b = [0,0,1]$$$.

В третьем примере $$$b = [1,0,4]$$$ недопустимо, потому что у вас всего $$$k = 4$$$ открытки с пожеланиями.

В четвертом примере одним из оптимальных способов распределить открытки с пожеланиями является использование $$$b = [2,0,5,0,0]$$$, при котором Маленькая А получит $$$2+2+5+5+5=19$$$ счастья.