DJ Genki vs Gram - Einherjar Joker

⠀

You have some cards. An integer between $$$1$$$ and $$$n$$$ is written on each card: specifically, for each $$$i$$$ from $$$1$$$ to $$$n$$$, you have $$$a_i$$$ cards which have the number $$$i$$$ written on them.

There is also a shop which contains unlimited cards of each type. You have $$$k$$$ coins, so you can buy at most $$$k$$$ new cards in total, and the cards you buy can contain any integer between $$$\mathbf{1}$$$ and $$$\mathbf{n}$$$, inclusive.

After buying the new cards, you must partition all your cards into decks, according to the following rules:

all the decks must have the same size;
there are no pairs of cards with the same value in the same deck.

Find the maximum possible size of a deck after buying cards and partitioning them optimally.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$, $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$0 \leq k \leq 10^{16}$$$) — the number of distinct types of cards and the number of coins.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^{10}$$$, $$$\sum a_i \geq 1$$$) — the number of cards of type $$$i$$$ you have at the beginning, for each $$$1 \leq i \leq n$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single integer: the maximum possible size of a deck if you operate optimally.

Note

In the first test case, you can buy one card with the number $$$1$$$, and your cards become $$$[1, 1, 1, 1, 2, 2, 3, 3]$$$. You can partition them into the decks $$$[1, 2], [1, 2], [1, 3], [1, 3]$$$: they all have size $$$2$$$, and they all contain distinct values. You can show that you cannot get a partition with decks of size greater than $$$2$$$, so the answer is $$$2$$$.

In the second test case, you can buy two cards with the number $$$1$$$ and one card with the number $$$3$$$, and your cards become $$$[1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 5, 5, 5, 5]$$$, which can be partitioned into $$$[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 2, 5], [2, 3, 5], [2, 4, 5]$$$. You can show that you cannot get a partition with decks of size greater than $$$3$$$, so the answer is $$$3$$$.

✓	#	Name		✎	Rating↕	Solved↕
	2097A	Sports Betting 2-sat brute force math sortings			1400	8.9k
	2018A	Cards Partition 2-sat brute force greedy implementation math			1600	12.9k

Problemset