您正在参加另一场锦标赛。有 $$$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$$$。