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

Есть вендинговый аппарат, в котором продаётся лимонад. Всего в аппарате есть $$$n$$$ ячеек. Вы знаете, что изначально в $$$i$$$-й ячейке находится $$$a_i$$$ банок лимонада. Также в аппарате есть $$$n$$$ кнопок, каждая кнопка соответствует какой-то ячейке, при этом каждой ячейке соответствует ровно одна кнопка. К сожалению, обозначения на кнопках стёрлись, поэтому вы не знаете, какая кнопка соответствует какой ячейке.

Когда вы нажимаете на кнопку, соответствующую $$$i$$$-й ячейке, происходит одно из двух событий:

  • Если в $$$i$$$-й ячейке есть банка лимонада, то она выпадет, и вы заберёте её себе. При этом количество банок лимонада в $$$i$$$-й ячейке уменьшится на $$$1$$$.
  • Если в $$$i$$$-й ячейке не осталось банок лимонада, то ничего не выпадет.

После нажатия банка выпадает так быстро, что отследить, из какой именно ячейки она выпала, невозможно. Содержимое ячеек скрыто от ваших глаз, поэтому вы не можете видеть, сколько банок осталось в каждой из ячеек. Единственное, что вам известно, это изначальные количества банок в ячейках: $$$a_1, a_2, \ldots, a_n$$$.

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

Обратите внимание, что вы можете адаптировать свою стратегию в процессе нажатия на кнопки, основываясь на том, выпала вам банка или нет. Гарантируется, что всего в аппарате есть хотя бы $$$k$$$ банок лимонада. Иными словами, $$$k \leq a_1 + a_2 + \ldots + a_n$$$.

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

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

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

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

Гарантируется, что $$$k \leq a_1 + a_2 + \ldots + a_n$$$, то есть всего в аппарате есть хотя бы $$$k$$$ банок лимонада.

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

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

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

Пример
Входные данные
5
2 1
1 1
2 2
1 2
3 4
2 1 3
10 50
1 1 3 8 8 9 12 13 27 27
2 1000000000
1000000000 500000000
Выходные данные
1
2
5
53
1000000000
Примечание

В первом наборе входных данных мы можем просто нажать на первую кнопку и получить банку лимонада.

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

В третьем наборе входных данных одна из оптимальных стратегий такова:

Нажимаем на первую кнопку дважды. После первого нажатия гарантированно выпадет банка лимонада. Далее есть два варианта:

  • Если после второго нажатия не выпала банка лимонада, то мы знаем, что эта кнопка обязательно соответствует второй ячейке, так как $$$a_2 = 1$$$ и $$$a_1, a_3 > 1$$$. Тогда мы можем нажать на вторую кнопку два раза, а на третью кнопку один раз. Так как $$$a_1, a_3 \geq 2$$$, то мы гарантированно получим три банки лимонада за эти три нажатия. Таким образом, за $$$5$$$ нажатий мы получим $$$4$$$ банки лимонада.
  • Если после второго нажатия выпала банка лимонада, то мы можем сделать одно нажатие на вторую кнопку и одно нажатие на третью кнопку. После каждого из этих нажатий мы гарантированно получим банку лимонада. Таким образом, за $$$4$$$ нажатия мы получим $$$4$$$ банки лимонада.

Можно показать, что за $$$4$$$ нажатия невозможно гарантированно получить $$$4$$$ банки лимонада, поэтому ответ $$$5$$$.