#P1783C. Yet Another Tournament
-
ID: 319
Type: RemoteJudge
2000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: 5
Uploaded By:
Hydro
Tags> Yet Another Tournament
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.
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.
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.
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
2
6
4
1
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$.