CF1783C.Yet Another Tournament

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.

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

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.

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