← 返回题目列表

Codeforces · 1783/C

C. 又一场锦标赛

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

您正在参加另一场锦标赛。有 $$$n + 1$$$ 参与者:您和 $$$n$$$ 其他对手,编号从 $$$1$$$ 到 $$$n$$$。

每两名参与者将互相对战一次。如果对手 $$$i$$$ 与对手 $$$j$$$ 比赛,当且仅当 $$$i > j$$$ 时他获胜。

当对手 $$$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$$$ 分钟,请打印您可以占据的最小位置。

示例

输入 #1

5
4 401
100 100 200 1
3 2
1 2 3
5 0
1 1 1 1 1
4 0
0 1 1 1
4 4
1 2 2 1

输出 #1

1
2
6
4
1

注意

在第一个测试用例中,您可以为所有对手做好准备,因此您将赢得 $$$4$$$ 场比赛并获得 $$$1$$$ 位,因为所有对手赢得的比赛不超过 $$$3$$$ 场。

在第二个测试用例中,您可以准备对抗第二个对手并获胜。结果,您将 $$$1$$$ 获胜,对手 $$$1$$$ — $$$1$$$ 获胜,对手 $$$2$$$ — $$$1$$$ 获胜,对手 $$$3$$$ — $$$3$$$ 获胜。因此,对手 $$$3$$$ 将获得 $$$1$$$ 位,而所有其他参与者,包括您在内,将获得 $$$2$$$ 位。

在第三个测试用例中,你根本没有时间准备,所以你会输掉所有游戏。由于每个对手至少赢了 $$$1$$$,因此您将获得最后的位置(位置 $$$6$$$)。

在第四个测试用例中,你没有时间准备,但你仍然可以战胜第一个对手。结果,对手 $$$1$$$ 没有获胜,您有 $$$1$$$ 获胜,而所有其他人至少有 $$$2$$$ 获胜。所以你的位置是$$$4$$$。