---

题意回顾

你有 $n$ 种数字的卡牌，第 $i$ 种有 $a_i$ 张。
你可以购买最多 $k$ 张新卡牌（数字任意）。
之后，将所有卡牌分成若干副套牌，要求：

1. 所有套牌大小相同（记为 $s$）；
2. 每副套牌内，数字互不相同。

求最大可能的 $s$。

---

关键观察

• 因为只有 $n$ 种数字，所以每副套牌最多包含 $n$ 张牌（每种数字最多一张），因此 答案 $s \le n$。

---

第一步：$k=0$ 的情况（不购买）

设：

• 总卡牌数 $m = \sum_{i=1}^n a_i$；
• 最大频率 $x = \max(a_i)$。

要能分成大小为 $s$ 的套牌，必须满足：

1. $s \mid m$（总牌数能被 $s$ 整除，才能正好分完）；
2. $x \le \frac{m}{s}$（每种数字最多出现在每副牌一次，所以最多只能有 $\frac{m}{s}$ 副牌，即每种数字最多 $\frac{m}{s}$ 张）。

证明（充分性）：
如果上述两条件成立，设 $d = m/s$ 为套牌数量。
每次从剩余牌中选 $s$ 种不同的牌（优先选剩余数量最多的 $s$ 种）组成一副牌，可以证明这个过程能一直进行下去（类似 1954D - Colored Balls 或 abc227_d - Project Planning 的贪心构造）。

因此，$k=0$ 时，能分出的最大 $s$ 是满足以上两个条件的最大 $s$。

---

第二步：一般 $k$ 的情况

我们想判断能否让套牌大小达到某个 $s$。

设最终套牌数为 $d = \frac{\text{总牌数}}{s}$。

由于每种数字在每副牌中最多出现一次，所以最终每种数字的牌数不能超过 $d$。

因此，对于第 $i$ 种数字：

• 如果 $a_i > d$，我们必须通过购买来增加别的数字，但无法减少 $a_i$，所以 $d$ 必须 $\ge a_i$？
  不对，我们无法降低 $a_i$，但可以通过买其他牌来让 $d$ 变大？
  其实 $d$ 是最终总牌数除以 $s$，而 $s$ 是我们试的值，$d$ 会变化。
  更直接的方法：

---

关键推导

最终套牌数 $d$ 满足：

• 每副牌大小 $s$，共 $d$ 副牌，总牌数 $= s \cdot d$。
• 每种数字最多出现 $d$ 次，所以原来就多的数字（$a_i > d$）已经超过了允许值，除非我们买其他牌来增加 $d$？
  不，$d$ 是全局的，$a_i$ 是固定的（未买之前），买卡只能增加总牌数，但每种数字的最终张数 = $a_i + \text{购买数量}_i$，这必须 $\le d$。

因此，对每种 $i$，需要购买的数量至少为 $\max(0, d - a_i)$。
总购买量：

$$\text{need} = \sum_{i=1}^n \max(0, d - a_i)$$

必须满足 $\text{need} \le k$。

同时，总牌数 = $\sum a_i + \text{购买量} = m + \text{购买量}$，并且等于 $s \cdot d$。

所以：

$$s \cdot d = m + \text{购买量}$$

其中 $0 \le \text{购买量} \le k$。

---

换一个角度（更常用）

我们想判断 $s$ 是否可行。

设 $d = \lceil \frac{\max(a_i)}{s} \rceil$？
不对，更常见的方法：

最终套牌数 $d$ 必须 $\ge \max(a_i)$，因为每种数字最多 $d$ 张。
同时，总牌数 = $s \cdot d \ge m$。

我们可以自由买卡，所以最终总牌数可以是 $m$ 到 $m+k$ 之间的任意值（只要不超 $k$ 张）。

因此，对给定的 $s$，我们想找 $d$ 满足：

1. $d \ge \max(a_i)$；
2. $s \cdot d \ge m$；
3. $s \cdot d \le m + k$（因为最多买 $k$ 张）；
4. 并且购买量 = $s \cdot d - m \le k$（这其实就是条件 3）。

还要检查每种数字的最终张数 $\le d$：
对每个 $i$，最终张数 = $a_i + \text{买}_i$，我们可以控制买多少张 $i$，只要总购买量 $\le k$。
最紧张的情况是 $a_i$ 很大，比如 $a_i > d$，那不可能，因为即使不买这种，它已经超过 $d$ 了。
所以必须有：

$$\max(a_i) \le d$$

即 $d \ge \max(a_i)$，这正是条件 1。

因此，$s$ 可行的条件是：存在整数 $d$ 使得：

• $d \ge \max(a_i)$；
• $s \cdot d \ge m$；
• $s \cdot d \le m + k$。

---

化简

从 $d \ge \max(a_i)$ 和 $s \cdot d \ge m$ 得：

$$d \ge \max\left(\max(a_i), \lceil \frac{m}{s} \rceil \right) $$

令 $d_{\min} = \max\left(\max(a_i), \lceil \frac{m}{s} \rceil \right)$。

那么需要存在 $d \ge d_{\min}$ 且 $s \cdot d \le m + k$。

最小的 $s \cdot d$ 在 $d = d_{\min}$ 时取得，为 $s \cdot d_{\min}$。
如果 $s \cdot d_{\min} \le m + k$，那么我们可以取 $d = d_{\min}$ 并购买 $s \cdot d_{\min} - m$ 张牌（这个数 $\ge 0$ 且 $\le k$）。
如果 $s \cdot d_{\min} > m + k$，那么即使取最小可能的 $d$ 也超过允许的总牌数，不可行。

因此，$s$ 可行的充要条件是：

$$s \cdot \max\left(\max(a_i), \lceil \frac{m}{s} \rceil \right) \le m + k $$

---

第三步：求解最大 $s$

由于 $s \le n$ 且 $n$ 的总和 $\le 2\times 10^5$，我们可以对每个测试用例从 $s = n$ 向下枚举第一个可行的 $s$，或者直接枚举 $s$ 并检查。

复杂度 $O(n)$ 每个测试用例（因为枚举 $s$ 并计算条件一次 $O(1)$）。

---

最终算法

对每个测试用例：

1. 计算 $m = \sum a_i$，$x = \max(a_i)$。
2. 对 $s$ 从 $n$ 往下到 $1$：
   • 计算 $d_{\min} = \max(x, \lceil m/s \rceil)$。
   • 如果 $s \cdot d_{\min} \le m + k$，输出 $s$ 并结束。

由于 $n$ 总和小，直接循环可行。

---

示例验证

以第一个样例： $n=3,k=1,a=[3,2,2]$
$m=7,x=3$。

• $s=3$：$d_{\min}=\max(3,\lceil7/3\rceil=3)=3$，$3\cdot3=9 > m+k=8$，不可行。
• $s=2$：$d_{\min}=\max(3,\lceil7/2\rceil=4)=4$，$2\cdot4=8 \le 8$，可行，输出 $2$。

匹配答案。

---

这样，我们就得到了一个清晰、可实现的 $O(n)$ 解法。