← 返回题目列表

Codeforces · 2018/A

A. 卡片分区

中文机器翻译题面 查看原题

你有一些牌。每张卡片上都写有 $$$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$$$。