Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

A. Разбиение карт
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
DJ Genki vs Gram - Einherjar Joker
⠀

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

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

После покупки новых карт вы должны разбить все свои карты на колоды согласно следующим правилам:

  • все колоды должны иметь одинаковый размер;
  • нет пары карт с одинаковым числом в одной колоде.

Найдите максимально возможный размер колоды после покупки карт и их оптимального разбиения.

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

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

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

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

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

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

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

Пример
Входные данные
9
3 1
3 2 2
5 4
2 6 1 2 4
2 100
1410065408 10000000000
10 8
7 4 6 6 9 3 10 2 8 7
2 12
2 2
2 70
0 1
1 0
1
3 0
2 1 2
3 1
0 3 3
Выходные данные
2
3
1
7
2
2
1
1
2
Примечание

В первом наборе входных данных вы можете купить одну карту с числом $$$1$$$, и ваш набор карт станет таким: $$$[1, 1, 1, 1, 2, 2, 3, 3]$$$. Вы можете разбить их на колоды $$$[1, 2], [1, 2], [1, 3], [1, 3]$$$. Они все имеют размер $$$2$$$, и все содержат разные значения. Можно показать, что невозможно получить разбиение с колодами размером больше $$$2$$$, поэтому ответ — $$$2$$$.

Во втором наборе входных данных вы можете купить две карты с числом $$$1$$$ и одну карту с числом $$$3$$$, и ваш набор карт станет таким: $$$[1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 5, 5, 5, 5]$$$. Его можно разбить на колоды $$$[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 2, 5], [2, 3, 5], [2, 4, 5]$$$. Можно показать, что нельзя получить разбиение с колодами размером больше $$$3$$$, поэтому ответ — $$$3$$$.