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

Вам задан целочисленный массив $$$a_1, a_2, \dots, a_n$$$ и целое число $$$k$$$.

За один шаг, вы можете

  • либо выбрать некоторый индекс $$$i$$$ и уменьшить $$$a_i$$$ на единицу (сделать $$$a_i = a_i - 1$$$);
  • либо выбрать два индекса $$$i$$$ и $$$j$$$ и присвоить элементу $$$a_i$$$ значение $$$a_j$$$ (сделать $$$a_i = a_j$$$).

За какое наименьшее количество шагов вы можете сделать сумму массива $$$\sum\limits_{i=1}^{n}{a_i} \le k$$$? (В массиве разрешены отрицательные элементы).

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

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

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

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

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

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

Для каждого набора выведите одно число — наименьшее количество шагов для получения $$$\sum\limits_{i=1}^{n}{a_i} \le k$$$.

Пример
Входные данные
4
1 10
20
2 69
6 9
7 8
1 2 1 3 1 2 1
10 1
1 2 3 1 2 6 1 6 8 10
Выходные данные
10
0
2
7
Примечание

В первом наборе входных данных, вам нужно уменьшить $$$a_1$$$ $$$10$$$ раз, чтобы получить сумму не более $$$k = 10$$$.

Во втором наборе, сумма массива $$$a$$$ уже не превосходит $$$69$$$, а потому вам не нужно ничего менять.

В третьем наборе, вы можете, например:

  1. присвоить $$$a_4 = a_3 = 1$$$;
  2. уменьшить $$$a_4$$$ на единицу, и получить $$$a_4 = 0$$$.
В результате вы получите массив $$$[1, 2, 1, 0, 1, 2, 1]$$$ с суммой, не превосходящей $$$8$$$, за $$$1 + 1 = 2$$$ шага.

В четвертом наборе, вы можете, например:

  1. выбрать $$$a_7$$$ и уменьшить его на один $$$3$$$ раза; вы получите $$$a_7 = -2$$$;
  2. выбрать $$$4$$$ элемента $$$a_6$$$, $$$a_8$$$, $$$a_9$$$ и $$$a_{10}$$$ и присвоить им значение $$$a_7 = -2$$$.
В результате вы получите массив $$$[1, 2, 3, 1, 2, -2, -2, -2, -2, -2]$$$ с суммой, меньше или равной $$$1$$$, за $$$3 + 4 = 7$$$ шагов.