P17297 [ICPC 2026 Xi'an I] Qenerals

Yuki 在玩一款叫做 Qenerals 的游戏。 第 $0$ 秒时，Yuki 拥有的士兵数量 $x = 0$，占领的堡垒数量 $y = 1$。地图上还有 $n$ 个未被占领的堡垒，第 $i$ 个堡垒的参数为 $a_i$。 游戏一共会进行 $m$ 秒。对于每个不大于 $m$ 的正整数 $i$： - 在第 $i$ 秒开始时，每个 Yuki 所占领的堡垒都会为 Yuki 生产 $1$ 个士兵，即 $x \leftarrow x + y$。 - 在第 $i$ 秒结束时，Yuki 可以进行任意次操作（可以为 $0$ 次）；每次操作，Yuki 需要选择一个未被占领的堡垒 $j$ 满足 $a_j \le x$，接着消耗 $a_j$ 个士兵并占领第 $j$ 个堡垒，即 $x \leftarrow x - a_j$ 且 $y \leftarrow y + 1$。 你需要帮助 Yuki 求出，在游戏结束后，她最多能拥有多少个士兵。

本题包含多组测试数据。 第一行包含一个正整数 $t$ $(1 \le t \le 10^5)$，表示测试数据组数。 对于每组测试数据： - 第一行包含两个正整数 $n, m$ $(1 \le n \le 5\cdot10^5,\ 1 \le m \le 10^{9})$。 - 第二行包含 $n$ 个正整数 $a_1, \dots, a_n$ $(1 \le a_i \le 10^9)$。 保证所有测试数据中 $n$ 的总和不超过 $5\cdot10^5$。

对于每组测试数据，输出一行，包含一个整数，表示在游戏结束后 Yuki 最多能拥有的士兵数量。

对于第 $1$ 组测试数据： - 在第 $1$ 秒开始时，Yuki 占领的堡垒数 $y = 1$，因此 Yuki 拥有的士兵数量 $x$ 由 $0$ 变为了 $1$。 - 在第 $1$ 秒结束时，Yuki 可以选择占领第 $2$ 个堡垒，因此 Yuki 占领的堡垒数 $y$ 由 $1$ 变为了 $2$，拥有的士兵数量 $x$ 由 $1$ 变为了 $0$。 - 在第 $2$ 秒开始时，Yuki 占领的堡垒数 $y = 2$，因此 Yuki 拥有的士兵数量 $x$ 由 $0$ 变为了 $2$。 - 在第 $2$ 秒结束时，Yuki 可以选择不进行任何操作。 - 在第 $3$ 秒开始时，Yuki 占领的堡垒数 $y = 2$，因此 Yuki 拥有的士兵数量 $x$ 由 $2$ 变为了 $4$。 - 在第 $3$ 秒结束时，Yuki 可以选择不进行任何操作。 - 在游戏结束后，Yuki 拥有的士兵数量 $x$ 达到了 $4$。可以证明，在游戏结束后 Yuki 最多能拥有的士兵数量即为 $4$。 对于第 $2$ 组测试数据： - Yuki 可以在第 $1,2,3$ 秒时分别占领第 $1,2,3$ 个堡垒，使 Yuki 在游戏结束后拥有的士兵数量达到 $13$。 对于第 $3$ 组测试数据： - Yuki 可以在第 $1$ 秒时占领第 $1$ 个堡垒，并在第 $2$ 秒时占领第 $2$ 个堡垒和第 $3$ 个堡垒，使 Yuki 在游戏结束后拥有的士兵数量达到 $12$。