Yet Another Tournament

2000ms

262144K

Description:

You are participating in Yet Another Tournament. There are $$$n + 1$$$ participants: you and $$$n$$$ other opponents, numbered from $$$1$$$ to $$$n$$$.

Each two participants will play against each other exactly once. If the opponent $$$i$$$ plays against the opponent $$$j$$$, he wins if and only if $$$i > j$$$.

When the opponent $$$i$$$ plays against you, everything becomes a little bit complicated. In order to get a win against opponent $$$i$$$, you need to prepare for the match for at least $$$a_i$$$ minutes — otherwise, you lose to that opponent.

You have $$$m$$$ minutes in total to prepare for matches, but you can prepare for only one match at one moment. In other words, if you want to win against opponents $$$p_1, p_2, \dots, p_k$$$, you need to spend $$$a_{p_1} + a_{p_2} + \dots + a_{p_k}$$$ minutes for preparation — and if this number is greater than $$$m$$$, you cannot achieve a win against all of these opponents at the same time.

The final place of each contestant is equal to the number of contestants with strictly more wins $$$+$$$ $$$1$$$. For example, if $$$3$$$ contestants have $$$5$$$ wins each, $$$1$$$ contestant has $$$3$$$ wins and $$$2$$$ contestants have $$$1$$$ win each, then the first $$$3$$$ participants will get the $$$1$$$-st place, the fourth one gets the $$$4$$$-th place and two last ones get the $$$5$$$-th place.

Calculate the minimum possible place (lower is better) you can achieve if you can't prepare for the matches more than $$$m$$$ minutes in total.

Input:

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 5 \cdot 10^5$$$; $$$0 \le m \le \sum\limits_{i=1}^{n}{a_i}$$$) — the number of your opponents and the total time you have for preparation.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 1000$$$), where $$$a_i$$$ is the time you need to prepare in order to win against the $$$i$$$-th opponent.

It's guaranteed that the total sum of $$$n$$$ over all test cases doesn't exceed $$$5 \cdot 10^5$$$.

Output:

For each test case, print the minimum possible place you can take if you can prepare for the matches no more than $$$m$$$ minutes in total.

Sample Input:

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

Sample Output:

Note:

In the first test case, you can prepare to all opponents, so you'll win $$$4$$$ games and get the $$$1$$$-st place, since all your opponents win no more than $$$3$$$ games.

In the second test case, you can prepare against the second opponent and win. As a result, you'll have $$$1$$$ win, opponent $$$1$$$ — $$$1$$$ win, opponent $$$2$$$ — $$$1$$$ win, opponent $$$3$$$ — $$$3$$$ wins. So, opponent $$$3$$$ will take the $$$1$$$-st place, and all other participants, including you, get the $$$2$$$-nd place.

In the third test case, you have no time to prepare at all, so you'll lose all games. Since each opponent has at least $$$1$$$ win, you'll take the last place (place $$$6$$$).

In the fourth test case, you have no time to prepare, but you can still win against the first opponent. As a result, opponent $$$1$$$ has no wins, you have $$$1$$$ win and all others have at least $$$2$$$ wins. So your place is $$$4$$$.

Informação

Provedor Codeforces

Código CF1783C