A. 卡牌分组

每个测试的时间限制： $2$ 秒
内存限制： $256$ 兆字节

题目描述

你有一些卡牌，每张卡牌上写着一个介于 $1$ 和 $n$ 之间的整数。具体来说，对于每个 $i$ 从 $1$ 到 $n$ ，你有 $a_i$ 张写有数字 $i$ 的卡牌。

此外，有一家商店，其中每种数字的卡牌数量是无限的。你有 $k$ 枚硬币，因此你最多可以购买 $k$ 张新卡牌，并且你购买的卡牌可以是 $1$ 到 $n$ 之间的任意整数。

购买新卡牌后，你必须将所有卡牌按照以下规则分组成若干“套牌”：

你需要求出在最优购买卡牌和最优分组方案下，套牌的最大可能大小。

每个测试点包含多个测试用例。第一行包含一个整数 $t$ （ $1 \le t \le 10^4$ ），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k$ （ $1 \le n \le 2 \cdot 10^5$ ， $0 \le k \le 10^{16}$ ），分别表示不同卡牌数字的种类数和你的硬币数。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ （ $0 \le a_i \le 10^{10}$ ， $\sum a_i \ge 1$ ），表示初始时你拥有的数字 $i$ 的卡牌数量。

保证所有测试用例的 $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

输出

在第一个测试用例中，你可以购买 $1$ 张数字为 $1$ 的卡牌，此时你的卡牌变为 $[1,1,1,1,2,2,3,3]$ 。你可以将它们分成 $[1,2],[1,2],[1,3],[1,3]$ 四副套牌：每副大小都是 $2$ ，且每副内的数字互不相同。可以证明无法得到大小大于 $2$ 的套牌，因此答案是 $2$ 。
在第二个测试用例中，你可以购买 $2$ 张数字为 $1$ 的卡牌和 $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$ 。