CF1783C Yet Another Tournament

你正在参加 Yet Another Tournament。有 $n+1$ 名参赛者：你和其他 $n$ 名对手，编号从 $1$ 到 $n$。 每两名参赛者之间会进行且仅进行一次比赛。如果对手 $i$ 与对手 $j$ 对战，只有当 $i > j$ 时，$i$ 才能获胜。 当对手 $i$ 和你对战时，情况会变得复杂。你想要战胜对手 $i$，需要至少准备 $a_i$ 分钟，否则你会输给该对手。 你总共有 $m$ 分钟用于准备比赛，但你每次只能为一场比赛做准备。换句话说，如果你想战胜对手 $p_1, p_2, \dots, p_k$，你需要花费 $a_{p_1} + a_{p_2} + \dots + a_{p_k}$ 分钟准备——如果这个时间超过 $m$，你就无法同时战胜所有这些对手。 每位选手的最终名次等于胜场数严格多于他的人数 $+1$。例如，如果有 $3$ 名选手各赢了 $5$ 场，$1$ 名选手赢了 $3$ 场，$2$ 名选手各赢了 $1$ 场，那么前 $3$ 名获得第 $1$ 名，第 $4$ 名获得第 $4$ 名，最后两名获得第 $5$ 名。 请计算在总准备时间不超过 $m$ 分钟的情况下，你能取得的最小可能名次（名次越小越好）。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 5 \cdot 10^5$；$0 \le m \le \sum\limits_{i=1}^{n}{a_i}$），分别表示你的对手数量和你可用于准备的总时间。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 1000$），其中 $a_i$ 表示你想要战胜第 $i$ 个对手所需的准备时间。 保证所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示在总准备时间不超过 $m$ 分钟的情况下，你能取得的最小可能名次。

在第一个测试用例中，你可以为所有对手做准备，因此你能赢得 $4$ 场比赛，并获得第 $1$ 名，因为所有对手最多只能赢 $3$ 场。 在第二个测试用例中，你可以只为第二个对手做准备并获胜。结果是你赢了 $1$ 场，对手 $1$ 赢了 $1$ 场，对手 $2$ 赢了 $1$ 场，对手 $3$ 赢了 $3$ 场。因此，对手 $3$ 获得第 $1$ 名，其他所有人（包括你）获得第 $2$ 名。 在第三个测试用例中，你没有时间准备，因此会输掉所有比赛。由于每个对手至少赢 $1$ 场，你会获得最后一名（第 $6$ 名）。 在第四个测试用例中，你没有时间准备，但你可以战胜第一个对手。结果是对手 $1$ 没有胜场，你赢了 $1$ 场，其他所有人至少赢了 $2$ 场。因此你的名次是第 $4$ 名。 由 ChatGPT 4.1 翻译