CF2018A.Cards Partition

DJ Genki vs Gram - Einherjar Joker

⠀

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

商店中提供无限量的各类卡片。你拥有 $k$ 枚硬币，因此最多可以购买 $k$ 张新卡片，购买的卡片可以包含 $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$）——表示初始时你拥有的各类卡片数量，其中 $1 \leq i \leq n$。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数：表示在最优操作下牌组可能的最大大小。

在第一个测试用例中，你可以购买一张写有数字 $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, 4]$，可以分配为 $[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 2, 5], [2, 3, 5], [2, 4, 5]$。可以证明无法得到大小大于 $3$ 的分配方案，因此答案为 $3$。

翻译由 DeepSeek R1 完成