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.


-----Examples-----

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

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Sorting

Greedy algorithms


Solutions:
def solve(N, M, arr):
	arr_sorted = sorted(arr)
	_sum = 0
	for (idx, a) in enumerate(arr_sorted + [0]):
		_sum += a
		if _sum > M:
			break
	if idx == 0:
		return N + 1
	elif idx == N:
		return 1
	_sum = sum(arr_sorted[:idx])
	tmp = arr_sorted[idx - 1]
	if _sum - tmp + arr[idx] <= M:
		return N - idx
	else:
		return N - idx + 1
T = int(input())
for _ in range(T):
	(N, M) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	ans = solve(N, M, arr)
	print(ans)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	l1 = sorted(l)
	sm = 0
	for x in range(n):
		sm += l1[x]
		if sm > k:
			if x != 0:
				sm -= l1[x] + l1[x - 1]
			sm += l[x]
			break
	if sm <= k:
		print(n - x)
	else:
		print(n - x + 1)


from itertools import accumulate
import bisect
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split(' ')))
	srted = sorted(arr)
	pref = list(accumulate(srted))
	ind = bisect.bisect_right(pref, m)
	if ind == n:
		print(1)
	elif ind == 0:
		print(n + 1)
	else:
		higherTime = max(srted[:ind])
		rem = m - pref[ind - 1]
		if rem + higherTime >= arr[ind]:
			print(n - ind)
		else:
			print(n - ind + 1)


testcases = int(input())
for _ in range(testcases):
	(n, m) = map(int, input().split())
	prep = list(map(int, input().split()))
	sorted_prep = sorted(prep)
	sum_prep = 0
	max_wins = n
	for i in range(n):
		sum_prep += sorted_prep[i]
		if sum_prep > m:
			max_wins = i
			break
	if max_wins == n:
		print(1)
	else:
		min_prep = sum(sorted_prep[:max_wins - 1])
		if min_prep + prep[max_wins] <= m:
			print(n - max_wins)
		else:
			print(n + 1 - max_wins)


import time
import sys

def find_place(arr, m):
	win_count = 0
	for i in range(len(arr)):
		if arr[i] > m:
			break
		m -= arr[i]
		win_count += 1
	return (win_count, m)

def main(input, print, end_line):
	t = int(input())
	for _ in range(t):
		(n, m) = map(int, input().split())
		arr = list(map(int, input().split()))
		arr_sort = list(arr)
		arr_sort.sort()
		(place, mm) = find_place(arr_sort, m)
		if place != 0 and place != n and (mm + arr_sort[place - 1] >= arr[place]):
			place += 1
		print(str(n + 1 - place) + end_line)
main(sys.stdin.readline, sys.stdout.write, '\n')


def main(a, m, n):
	ordered = a.copy()
	ordered.sort()
	(i, remaining) = (0, m)
	while i < n and ordered[i] <= remaining:
		remaining -= ordered[i]
		i += 1
	if i == 0:
		print(n + 1)
		return
	i -= 1
	rank = n - i
	if rank > 1 and a[i + 1] - ordered[i] <= remaining:
		rank -= 1
	print(rank)
tests = int(input())
for _ in range(tests):
	(n, m) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	main(a, m, n)


def solve(a, m, n):
	v = sorted(a)
	nwin = 0
	for ni in range(n):
		if m < v[ni]:
			break
		m -= v[ni]
		nwin += 1
	pos = 1 + n - nwin
	if nwin > 0 and nwin < n:
		if m + v[nwin - 1] >= a[nwin]:
			pos -= 1
	return pos
t = int(input())
ans = []
for ti in range(t):
	(n, m) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	ans.append(solve(a, m, n))
for a in ans:
	print(a)


for time in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(j) for j in input().split()]
	b = sorted(a)
	num = 0
	for s in b:
		if s > k:
			break
		k -= s
		num += 1
	if len(b) == num:
		print(1)
		continue
	if num == 0:
		print(n + 1)
		continue
	if a[num] <= b[num - 1] + k:
		num += 1
	print(n - num + 1)


def ii(num=False):
	i = input().split()
	if num:
		return int(i[0])
	try:
		return list(map(int, i))
	except Exception:
		return i

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
for _ in range(ii(1)):
	(n, m) = ii()
	a = ii()
	b = list(a)
	b.sort()
	ans = 0
	for i in b:
		if i <= m:
			ans += 1
			m -= i
		else:
			break
	if ans != n and ans != 0 and (b[ans - 1] + m >= a[ans]):
		ans += 1
	print(n + 1 - ans)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = sorted(a)
	ans = 0
	for i in range(n):
		if m >= b[i]:
			ans += 1
			m -= b[i]
	if ans not in [0, n] and b[ans - 1] + m >= a[ans]:
		ans += 1
	print(n - ans + 1)


testcases = int(input())
for _ in range(testcases):
	(n, m) = map(int, input().split())
	prep = list(map(int, input().split()))
	sorted_prep = sorted(prep)
	ps = [0]
	max_wins = n
	for (i, num) in enumerate(sorted_prep):
		ps.append(ps[i] + num)
		if ps[-1] > m:
			max_wins = i
			break
	if max_wins == n:
		print(1)
	else:
		min_prep = ps[max_wins - 1]
		if min_prep + prep[max_wins] <= m:
			print(n - max_wins)
		else:
			print(n + 1 - max_wins)


for _ in range(int(input())):
	(n, m) = map(int, input().split(' '))
	l = list(map(int, input().split(' ')))
	l2 = l.copy()
	l.sort()
	ans = 0
	for i in range(n):
		if m < l[i]:
			break
		else:
			m -= l[i]
			ans += 1
	if ans != 0 and ans != n and (m + l[ans - 1] >= l2[ans]):
		ans += 1
	print(n + 1 - ans)


from bisect import bisect_left, bisect_right
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	cpy = list(arr)
	arr.sort()
	for i in range(1, n):
		arr[i] += arr[i - 1]
	W = bisect_right(arr, m)
	ans = n + 1 - W
	if W > 0 and m >= (arr[W - 2], 0)[W == 1] + cpy[W - int(W == n)]:
		ans -= 1
	print(max(1, ans))


import sys
input = sys.stdin.readline
T = int(input())
ans = [0] * T
for t in range(T):
	(n, m) = map(int, input().split())
	b = list(map(int, input().split()))
	a = sorted(b)
	win = 0
	while win < n and m >= a[win]:
		m -= a[win]
		win += 1
	if win not in [0, n] and a[win - 1] + m >= b[win]:
		ans[t] = n - win
	else:
		ans[t] = n - win + 1
print('\n'.join(map(str, ans)))


tests = int(input())
for j in range(tests):
	(n, m) = list(map(int, input().split()))
	a1 = list(map(int, input().split()))
	a = sorted(a1)
	k = 0
	for i in range(n):
		if a[i] <= m:
			m -= a[i]
			k += 1
		else:
			for Y in range(i):
				if a1[k] <= a[Y] + m:
					k += 1
					break
			break
	print(n - k + 1)


test = int(input())
for j in range(test):
	(x, m) = list(map(int, input().split()))
	a1 = list(map(int, input().split()))
	a = sorted(a1)
	k = 0
	for i in range(x):
		if a[i] <= m:
			m -= a[i]
			k += 1
		else:
			for j in range(i):
				if a1[k] <= a[j] + m:
					k += 1
					break
			break
	print(x - k + 1)


testcases = int(input())
for _ in range(testcases):
	(n, m) = map(int, input().split())
	prep = list(map(int, input().split()))
	sorted_prep = sorted(prep)
	sum_prep = 0
	max_wins = 0
	pot_wins = set()
	for num in sorted_prep:
		sum_prep += num
		if sum_prep <= m:
			max_wins += 1
			pot_wins.add(num)
		else:
			break
	if max_wins == n:
		print(1)
	elif prep[max_wins] in pot_wins:
		print(n - max_wins)
	else:
		min_prep = sum(sorted_prep[:max_wins - 1])
		if min_prep + prep[max_wins] <= m:
			print(n - max_wins)
		else:
			print(n + 1 - max_wins)


import sys
import math
from bisect import bisect_right as br
from collections import deque
from itertools import combinations as cb

def int_arr():
	return list(map(int, sys.stdin.readline().strip().split()))

def str_arr():
	return list(map(str, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	(n, k) = int_arr()
	arr = int_arr()
	cp = arr.copy()
	arr.sort()
	pref = []
	prev = 0
	for i in range(n):
		prev += arr[i]
		pref.append(prev)
	i = 0
	j = n - 1
	ans = -1
	while i <= j:
		mid = (i + j) // 2
		if mid == -1:
			break
		if pref[mid] <= k:
			ans = max(ans, mid)
			i = mid + 1
		else:
			j = mid - 1
	if ans == n - 1:
		print(1)
	elif ans == -1:
		print(n + 1)
	elif pref[ans] - arr[ans] + cp[ans + 1] <= k:
		print(n - ans - 1)
	else:
		print(n - ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	l = a[:]
	wins = 0
	a.sort()
	l1 = []
	for i in a:
		if i <= m:
			m = m - i
			wins += 1
			l1.append(i)
	j = wins
	temp_pos = n - j
	if j > n - 1:
		print(1)
	elif l[j] in l1:
		print(n - j)
	elif len(l1) > 0 and l[j] <= m + l1[-1]:
		print(n - j)
	else:
		print(n - j + 1)


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	(n, m) = map(int, sys.stdin.readline().split())
	a = list(map(int, sys.stdin.readline().split()))
	b = sorted(a)
	win = 0
	while win < n and m >= b[win]:
		m -= b[win]
		win += 1
	if win in [0, n] or b[win - 1] + m < a[win]:
		print(n - win + 1)
	else:
		print(n - win)


tc = int(input())
for _ in range(tc):
	(n, m) = map(int, input().split())
	lst = list(map(int, input().split()))
	arr = lst[:]
	lst.sort()
	coun = 0
	sm = 0
	while coun < n and sm + lst[coun] <= m:
		sm += lst[coun]
		coun += 1
	if coun > 0 and coun < n and (arr[coun] <= m - sm + lst[coun - 1]):
		print(n - coun)
	else:
		print(n - coun + 1)


for _ in range(int(input())):
	(n1, minutes) = input().split()
	(n1, minutes) = (int(n1), int(minutes))
	reqm = [int(a) for a in input().split()]
	origm = reqm.copy()
	reqm.sort()
	wins = 0
	for i in range(len(reqm)):
		if reqm[i] > minutes:
			break
		minutes -= reqm[i]
		wins += 1
	if wins != 0 and wins != len(reqm) and (minutes + reqm[wins - 1] >= origm[wins]):
		wins += 1
	print(n1 + 1 - wins)


t = int(input())
for p in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = a[:]
	a.sort()
	c = 0
	sum = 0
	flag = True
	for i in range(n):
		if sum + a[i] <= m:
			sum += a[i]
			c += 1
		else:
			flag = False
			break
	if flag:
		print(1)
	elif c != 0:
		count = b[c]
		for j in range(0, c - 1):
			count += a[j]
		if count > m:
			print(n - c + 1)
		else:
			print(n - c)
	else:
		print(n + 1)


t = int(input())
for _ in range(t):
	(n, m) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	new_a = a[:]
	a.sort()
	ost = m
	maxwins = 0
	wins = 0
	last = 0
	ind = 0
	le = 0
	for i in range(n):
		if ost - a[i] >= 0:
			ost -= a[i]
			maxwins += 1
		else:
			last = a[i - 1]
			ind = i
			break
	if 0 < maxwins < n and ost + last - new_a[maxwins] >= 0:
		maxwins += 1
	print(n - maxwins + 1)


def main():
	t = int(input())
	for _ in range(t):
		ans = solve()
		print(ans)

def solve():
	(n, m) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	sorta = sorted(a)
	k = calc(sorta, m)
	if k == n:
		return 1
	if k == 0:
		return n + 1
	m2 = m - a[k]
	if m2 < 0:
		return n - k + 1
	a2 = a[:k] + a[k + 1:]
	sorta2 = sorted(a2)
	k2 = calc(sorta2, m2)
	if k2 >= k - 1:
		return n - k
	else:
		return n - k + 1

def calc(sorta, m):
	curmins = 0
	k = 0
	n = len(sorta)
	for i in range(n):
		curmins += sorta[i]
		if curmins <= m:
			k += 1
		else:
			break
	return k
main()


from collections import Counter

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
tests = inp()
for i in range(tests):
	(n, time) = invr()
	input_arr = inlt()
	arr = input_arr.copy()
	arr.sort()
	ans = 0
	wins = 0
	max_spent = 0
	for j in range(n):
		if time >= arr[j]:
			time -= arr[j]
			max_spent = max(max_spent, arr[j])
			wins += 1
		else:
			ans = n - j
			break
	if wins < n and input_arr[wins] <= max_spent + time:
		ans -= 1
	print(ans + 1)


def solve(a, n, m):
	b = sorted(a)
	win = 0
	time = 0
	max_prepare_time = 0
	while time <= m and win < n:
		if time + b[win] > m:
			break
		time += b[win]
		max_prepare_time = max(max_prepare_time, b[win])
		win += 1
	if win == n:
		print(1)
		return
	if m - time >= a[win] - max_prepare_time:
		print(n - win)
	else:
		print(n - win + 1)
t = int(input())
for i in range(t):
	s = input()
	(n, m) = (int(s.split()[0]), int(s.split()[1]))
	a = [int(si) for si in input().split()]
	solve(a, n, m)


import sys
T = int(input())
for t in range(0, T):
	(n, m) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = sorted(a)
	i = 0
	s = 0
	for x in b:
		s += x
		if s <= m:
			i += 1
		else:
			break
	if i == 0:
		print(n + 1)
		continue
	elif i == n:
		print(1)
		continue
	j = 1
	s = a[i]
	if s > m:
		j = 0
	else:
		v = False
		for h in range(n):
			if b[h] == a[i] and v == False:
				v = True
				continue
			x = b[h]
			s += x
			if s <= m:
				j += 1
			else:
				break
	print(min(n - i + 1, n - j))


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	sorted_a = sorted(zip(a, [j for j in range(n)]), key=lambda x: x[0])
	mstar = 0
	wins = 0
	biggesta = 0
	for ai in sorted_a:
		mstar += ai[0]
		if mstar > m:
			mstar -= ai[0]
			break
		biggesta = ai[0]
		wins += 1
	if wins == n:
		print(1)
	elif wins == 0:
		print(n + 1)
	elif a[wins] <= m - mstar + biggesta:
		print(n - wins)
	else:
		print(n - wins + 1)


def main():
	t = int(input())
	for i in range(t):
		(n, m) = map(int, input().split())
		L = list(map(int, input().split()))
		M = [L[i] for i in range(n)]
		M.sort()
		counter = 0
		i = 0
		s = 0
		while s <= m and i < n:
			s += M[i]
			if s <= m:
				counter += 1
			i += 1
		if counter == n:
			print(1)
		elif counter == 0:
			print(n + 1)
		else:
			a = L[counter]
			del L[counter]
			m -= a
			M = [L[i] for i in range(n - 1)]
			M.sort()
			if m >= 0:
				counter1 = 1
			else:
				counter1 = 0
			i = 0
			s = 0
			while s <= m and i < n:
				s += M[i]
				if s <= m:
					counter1 += 1
				i += 1
			if counter1 == counter:
				print(n - counter)
			else:
				print(n - counter + 1)
main()


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	(*a,) = map(int, input().split())
	b = []
	for i in a:
		b += [i]
	b.sort()
	m_tmp = 0
	i = 0
	while i < n and m_tmp + b[i] <= m:
		m_tmp += b[i]
		i += 1
	max_pts = i
	if max_pts == 0:
		print(n + 1)
	elif max_pts == n:
		print(1)
	else:
		gar = n - max_pts + 1
		m_tmp = a[n - gar + 1]
		if m_tmp <= m:
			i = 0
			while m_tmp + b[i] <= m:
				m_tmp += b[i]
				i += 1
			if i >= max_pts - 1:
				gar -= 1
		print(gar)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = [(x, i) for (i, x) in enumerate(map(int, input().split()))]
	arr.sort(key=lambda x: x[0])
	sm = 0
	i = 0
	while i < n and sm <= m:
		sm += arr[i][0]
		i += 1
	if sm > m:
		sm -= arr[i - 1][0]
		i -= 1
	if any((x[1] == i for x in arr[:i])):
		print(n - i)
	elif i:
		p = int(1000000000.0)
		for x in arr:
			if x[1] == i:
				p = x[0]
				break
		print(n - i if sm - arr[i - 1][0] + p <= m else n - i + 1)
	else:
		print(n + 1)


import sys
input = sys.stdin.readline

def readList():
	return list(map(int, input().split()))

def readInt():
	return int(input())

def readInts():
	return map(int, input().split())

def readStr():
	return input().strip()

def solve():
	(n, m) = readInts()
	arr = readList()
	sa = sorted([(v, i) for (i, v) in enumerate(arr)], key=lambda x: (x[0], -x[1]))
	cnt = 0
	cap = m
	for i in range(n):
		if m >= sa[i][0]:
			cnt += 1
			m -= sa[i][0]
		else:
			break
	if cnt == n:
		return 1
	for i in range(n):
		if sa[i][1] == cnt:
			if i < cnt:
				return n - cnt
			elif cap < sa[i][0]:
				return n - cnt + 1
			else:
				cap -= sa[i][0]
				ans = 1
	for i in range(n):
		if sa[i][1] == cnt:
			continue
		if cap >= sa[i][0]:
			ans += 1
			cap -= sa[i][0]
		else:
			break
	return min(n - ans, n - cnt + 1)
for _ in range(int(input())):
	print(solve())


t = int(input().strip())
for _ in range(t):
	(n, m) = map(int, input().strip().split())
	a = list(map(int, input().strip().split()))
	prep = sorted([(a[i], i) for i in range(n)])
	tot = 0
	count = 0
	last = 0
	for pair in prep:
		tot += pair[0]
		if tot > m:
			tot -= pair[0]
			break
		else:
			last = pair[0]
			count += 1
	if count == 0:
		print(n + 1)
	elif count == n:
		print(1)
	elif count in [prep[j][1] for j in range(count)]:
		print(n - count)
	elif a[count] - last + tot <= m:
		print(n - count)
	else:
		print(n - count + 1)


def solve(n, m, a):
	wins = [k for k in range(n)]
	a = sorted([(prep, index) for (index, prep) in enumerate(a)])
	time_spent = 0
	player_wins = 0
	(defeated_anyone, last_defeated_prep, last_defeated_index) = (False, 0, 0)
	for (prep, index) in a:
		if time_spent + prep > m:
			if defeated_anyone and time_spent - last_defeated_prep + prep <= m and (wins[index] == player_wins):
				wins[last_defeated_index] += 1
				time_spent -= last_defeated_prep
				time_spent += prep
				(defeated_anyone, last_defeated_prep, last_defeated_index) = (True, prep, index)
			else:
				wins[index] += 1
		else:
			time_spent += prep
			player_wins += 1
			(defeated_anyone, last_defeated_prep, last_defeated_index) = (True, prep, index)
	return sum((win > player_wins for win in wins)) + 1
t = int(input())
for _ in range(t):
	(n, m) = [int(component) for component in input().split(' ')]
	a = [int(component) for component in input().split(' ')]
	print(solve(n, m, a))


import sys
import heapq
input = sys.stdin.readline

def main():
	for __ in range(int(input())):
		(n, m) = [int(xx) for xx in input().split()]
		a = [int(xx) for xx in input().split()]
		b = []
		for i in range(n):
			b.append((a[i], n - i))
		b = sorted(b)
		pr = [0]
		p = [i for i in range(n)]
		for i in range(n):
			pr.append(pr[-1] + b[i][0])
		for i in range(n + 1):
			if pr[i] > m:
				z = i - 1
				break
		else:
			z = n
		if z == n:
			print(1)
			continue
		if z == 0:
			print(n + 1)
			continue
		h = []
		s = 0
		ANS = n - z + 1
		if pr[z - 1] + a[z] <= m:
			ANS -= 1
		print(ANS)
main()


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	new_a = []
	for j in range(len(a)):
		new_a.append((j, a[j]))
	old_a = a[:]
	a = new_a
	a.sort(key=lambda x: x[1])
	s = 0
	players = set()
	palyers_won = 0
	for j in range(len(a)):
		if s + a[j][1] <= m:
			s += a[j][1]
			players.add(a[j][0])
		else:
			palyers_won = j
			break
	else:
		palyers_won = n
	place = n - palyers_won
	if place == 0:
		print(1)
		continue
	elif place == n:
		print(n + 1)
		continue
	if palyers_won not in players:
		if s - a[palyers_won - 1][1] + old_a[palyers_won] <= m:
			print(place)
			continue
		print(place + 1)
		continue
	print(place)


for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	b = a.copy()
	b.sort()
	c = [0] * (n + 1)
	for i in range(n):
		c[i + 1] = c[i] + b[i]
	ans = n + 1
	for x in range(1, n + 1):
		res = n - x
		if m >= c[x]:
			ans = min(n - x + 1, ans)
		if x < n and m >= c[x] + max(0, a[x] - b[x - 1]):
			ans = min(ans, max(1, n - x))
	print(ans)


import os
import math
import collections
import bisect
import functools
import itertools
import heapq

def solve(a, n, m):
	w = list(range(n + 1))
	b = sorted(([x, -(i + 1)] for (i, x) in enumerate(a)))
	tmp = m
	c = 0
	idx = 0
	while idx < n:
		x = b[idx][0]
		if tmp < x:
			break
		c += 1
		tmp -= x
		idx += 1
	if idx == n:
		return 1
	remain = tmp
	if idx > 0:
		remain += b[idx - 1][0]

	def valid(x):
		need = n + 1 - x
		if c >= need:
			return True
		if c < need - 1:
			return False
		return remain >= a[n - x]
	(l, r) = (1, n + 1)
	while l < r:
		mid = (l + r) // 2
		if valid(mid):
			r = mid
		else:
			l = mid + 1
	return l
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	print(solve(a, n, m))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	d = [i for i in range(n)]
	x = [[a[i], i] for i in range(n - 1, -1, -1)]
	x.sort()
	c = 0
	for i in range(n):
		if m >= x[i][0]:
			c += 1
			m -= x[i][0]
		else:
			d[x[i][1]] += 1
	ans = 1
	if c > 0 and c < n:
		t = x[c - 1][1] + 1
		pre = x[c - 1][0]
		m += pre
		ch = t - 1
		for i in range(c, c + 1):
			if a[i] <= m and d[i] == i + 1 and (d[i] == c + 1):
				ch = i
				break
		d[t - 1] += 1
		d[ch] -= 1
	for i in range(n):
		if d[i] > c:
			ans += 1
	print(ans)


tc = int(input())
for _ in range(tc):
	(n, m) = map(int, input().split())
	a = [[int(x), i] for (i, x) in enumerate(input().split())]
	ca = sorted(a)
	cm = m
	i = 0
	while i < n:
		if cm >= ca[i][0]:
			cm -= ca[i][0]
		else:
			break
		i += 1
	if i == n:
		print(1)
	else:
		rank = n - i
		if m >= a[i][0]:
			cm = m - a[i][0]
			(j, k) = (0, 0)
			while j + k < n:
				if ca[j + k][1] == i:
					k = 1
					continue
				if cm >= ca[j + k][0]:
					cm -= ca[j + k][0]
				else:
					break
				j += 1
		else:
			j = -2
		if j + 1 == i:
			print(rank)
		else:
			print(rank + 1)