你有一些牌。每张卡片上都写有 $$$1$$$ 和 $$$n$$$ 之间的整数:具体而言,对于从 $$$1$$$ 到 $$$n$$$ 的每张 $$$i$$$,您都有 $$$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$$$。
输出
对于每个测试用例,输出一个整数:如果您以最佳方式操作,则牌组的最大可能大小。
示例
输入 #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$$$ 的卡,您的卡将变为 $$$[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$$$。