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