A. Подсчет перестановок
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть несколько карточек, на каждой из которых написано целое число от $$$1$$$ до $$$n$$$. В частности, для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ у вас есть $$$a_i$$$ карточек, на которых написано число $$$i$$$.

Также есть магазин, который содержит неограниченное количество карточек каждого типа. У вас есть $$$k$$$ монет, поэтому вы можете купить в общей сложности $$$k$$$ дополнительных карточек, а купленные вами карточки могут содержать любые целые числа от $$$1$$$ до $$$n$$$.

После покупки новых карточек вы расставляете все свои карточки в линию. Счет расстановки — это количество (непрерывных) подмассивов длины $$$n$$$, которые являются перестановкой массива $$$[1, 2, \ldots, n]$$$. Какой максимальный счет вы можете получить?

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1\le n \le 2 \cdot 10^5$$$, $$$0\le k \le 10^{12}$$$) — количество различных типов карт и количество монет.

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

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

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

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

Пример
Входные данные
8
1 10
1
2 4
8 4
3 4
6 1 8
3 9
7 6 2
5 3
6 6 7 4 6
9 7
7 6 1 7 6 2 4 3 3
10 10
1 3 1 2 1 9 3 5 7 5
9 8
5 8 7 5 1 3 2 9 8
Выходные данные
11
15
15
22
28
32
28
36
Примечание

В первом наборе входных данных искомый (и единственный) массив, который можно получить, — это $$$[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]$$$ ($$$11$$$ карточек с числом $$$1$$$), который содержит $$$11$$$ подмассивов, состоящих из перестановки $$$[1]$$$.

Во втором наборе входных данных мы можем купить $$$0$$$ карточек типа $$$1$$$ и $$$4$$$ карточки типа $$$2$$$, а затем расставить карточки следующим образом: $$$[1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2]$$$. Есть $$$8$$$ подмассивов, равных $$$[1, 2]$$$, и $$$7$$$ подмассивов, равных $$$[2, 1]$$$, что в сумме составляет $$$15$$$ подмассивов, которые являются перестановкой $$$[1, 2]$$$. Можно также доказать, что это максимальный счет, который мы можем получить.

В третьем наборе входных данных одной из возможных оптимальных расстановок является $$$[3, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 3]$$$.