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

Вам задан массив целых чисел $$$a_1, a_2, a_3, \dots, a_n$$$. Ваша задача — сделать все элементы массива $$$a$$$ равными друг другу. Для этого вы можете выполнить следующую операцию не более чем $$$k$$$ раз:

  • выберите любой индекс $$$i$$$ от $$$1$$$ до $$$n$$$ и увеличьте $$$a_i$$$ на единицу.
Вы можете выбрать любой элемент массива, но если выбранный $$$a_i$$$ по значению строго больше, чем текущий минимум массива, вы заработаете одну монету.

Какое максимальное количество монет вы можете заработать среди всех возможных способов сделать все элементы массива равными?

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

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

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

Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — сам массив.

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

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

Для каждого набора входных данных, если сделать все элементы равными невозможно, выведите $$$-1$$$. В противном случае выведите максимальное количество монет, которое вы можете заработать, сделав все элементы равными.

Пример
Входные данные
4
3 16
1 10 2
4 20
6 2 4 9
5 9
7 7 7 7 7
2 1000000000000
1000000000 1000000000
Выходные данные
-1
11
0
499999999999
Примечание

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

Во втором наборе вы можете, например, увеличить $$$a_3 = 4$$$ до $$$10$$$, далее увеличить $$$a_1 = 6$$$ до $$$10$$$, потом $$$a_4 = 9$$$ до $$$10$$$ и, наконец, $$$a_2 = 2$$$ до $$$10$$$. Вы выполните $$$19$$$ операций и заработаете суммарно $$$(10 - 4) + (10 - 6) + (10 - 9) = 11$$$ монет, так как увеличение $$$a_2$$$ с $$$2$$$ до $$$10$$$ не принесет вам никаких монет.

В третьем наборе вы можете оставить массив без изменений или сделать все элементы равными $$$8$$$ — обе стратегии дадут вам $$$0$$$ монет.