题目描述

灯芯被唤醒后，护山明灯重新燃起，山中的迷雾开始消散。青禾与砚秋准备返程前，还要把随身的药材分装成若干个药囊，送给沿途受伤的村民。

药材共有 $n$ 种，编号为 $1$ 到 $n$。对于每个 $i$，他们已有 $a_i$ 份编号为 $i$ 的药材。

山下的药铺可以无限供应每一种药材。他们拥有 $k$ 枚铜钱，每枚铜钱可以购买一份药材，因此最多可以再购买 $k$ 份药材；每次购买时，可以任意选择编号 $1$ 到 $n$ 中的一种药材。

购买结束后，必须把拥有的所有药材分成若干个药囊，并满足以下条件：

• 每个药囊中药材的份数必须相同；
• 同一个药囊中不能出现两份编号相同的药材。

请你求出，在最优的购买和分装方案下，一个药囊最多可以装多少份药材。

输入格式

第一行包含一个整数 $t$，表示测试用例的数量。

对于每个测试用例：

• 第一行包含两个整数 $n,k$，分别表示药材种类数和铜钱数量；
• 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，其中 $a_i$ 表示初始拥有的第 $i$ 种药材数量。

输出格式

对于每个测试用例，输出一个整数，表示在最优操作下，一个药囊可能具有的最大药材份数。

输入输出样例

输入 #1

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

输出 #1

2
3
1
7
2
2
1
1
2

说明与限制

• $1\le t\le 10^4$
• $1\le n\le 2\cdot 10^5$
• $0\le k\le 10^{16}$
• $0\le a_i\le 10^{10}$
• $\sum a_i\ge 1$
• 所有测试用例中，$n$ 的总和不超过 $2\cdot 10^5$。

在第一个测试用例中，可以购买一份编号为 $1$ 的药材。此时可以把所有药材分成

四个药囊。每个药囊都装有 $2$ 份编号互不相同的药材，并且无法得到药囊大小大于 $2$ 的方案，因此答案为 $2$。

在第二个测试用例中，可以购买两份编号为 $1$ 的药材和一份编号为 $3$ 的药材。此时可以把所有药材分成

六个药囊。每个药囊都装有 $3$ 份编号互不相同的药材，并且无法得到药囊大小大于 $3$ 的方案，因此答案为 $3$。

至此，护山明灯重新亮起，迷雾散去。青禾与砚秋带着分装好的药囊踏上归途，「云岫寻灯记」也迎来了尾声。