Yet Another Tournament
Contest: Educational Codeforces Round 141 (Rated for Div. 2)
Difficulty rating: 1700
Tags: binary search, greedy, sortings

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 format:
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 format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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$$$.

Example 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

Example output:
1
2
6
4
1

Editorial:
Suppose, at the end, you won $$$x$$$ matches, what can be your final place? Look at each opponent $$$i$$$ with $$$i < x$$$ ($$$0$$$-indexed). Since the $$$i$$$-th opponent ($$$0$$$-indexed) won $$$i$$$ games against the other opponents, even if they win against you, they'll gain $$$i + 1 \le x$$$ wins in total and can't affect your place (since your place is decided by only opponents who won strictly more matches than you).
From the other side, let's look at each opponent $$$i$$$ with $$$i > x$$$ ($$$0$$$-indexed). Even if they lose to you, they still have $$$i > x$$$ wins (you have only $$$x$$$), so all of them have strictly more wins than you.
As a result, there is only one opponent $$$i = x$$$, whose match against you can affect your final place: if you won against them, your place will be $$$n - x$$$, otherwise your place will be $$$n - x + 1$$$.
Now, let's compare your possible places if you win $$$x$$$ games with places for winning only $$$x - 1$$$ games: $$$x$$$ wins gives you places $$$n - x$$$ or $$$n - x + 1$$$, while winning $$$x - 1$$$ leads you to places $$$n - x + 1$$$ or $$$n - x + 2$$$ that objectively worse.
In other words, it's always optimal to win as many matches as possible.
How to win the most number of games? It's to choose the easiest opponents. Let's sort array $$$a$$$ and find the maximum prefix $$$[0, x)$$$ with $$$a_0 + a_1 + \dots + a_{x-1} \le m$$$. So, we found maximum number of games $$$x$$$ we can win. The last is to check: can we get place $$$n - x$$$, or only $$$n - x + 1$$$.
If $$$a_x$$$ contains among $$$x$$$ smallest values, then we'll take place $$$n - x$$$. Otherwise, let's try to "insert" $$$a_x$$$ in this set, i. e. let's erase the biggest among them and insert $$$a_x$$$. If the sum is still lower or equal to $$$m$$$, it's success and we get place $$$n - x$$$. Otherwise, our place is $$$n - x + 1$$$.
The total complexity is $$$O(n \log{n})$$$ because of sorting.