Ved is a salesman. He needs to earn at least W rupees in N days for his livelihood. However, on a given day i (1 ≤ i ≤ N), he can only earn A_{i} rupees by working on that day. 

Ved, being a lazy salesman, wants to take as many holidays as possible. It is known that on a holiday, Ved does not work and thus does not earn anything. Help maximize the number of days on which Ved can take a holiday. 

It is guaranteed that Ved can always earn at least W rupees by working on all days.

------ Input Format ------ 

- The first line contains a single integer T - the number of test cases. Then the test cases follow.
- The first line of each test case contains two integers N and W - the size of the array A and the money Ved has to earn in those N days.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N} denoting the money which Ved can earn on each day.

------ Output Format ------ 

For each test case, output the maximum number of holidays Ved can take.

------ Constraints ------ 

$1 ≤T ≤100$
$1 ≤W ≤10000$
$1 ≤N ≤100$
$1 ≤A_{i} ≤100$
- It is guaranteed that Ved can always earn at least $W$ rupees by working on all days.

----- Sample Input 1 ------ 
3
5 10
3 2 6 1 3
4 15
3 2 4 6
6 8
9 12 6 5 2 2

----- Sample Output 1 ------ 
2
0
5

----- explanation 1 ------ 
Test case-1: Ved can work on $2$-nd, $3$-rd and $5$-th day earning $2 + 6 + 3 = 11$ rupees $≥ W$ rupees. Thus he can take $2$ holidays on the $1$-st and the $4$-th day.

Test case-2: Ved has to work on all days to earn $≥ W$ rupees. Thus he can not take any holidays.

Test case-3: Ved can work on $2$-nd day earning $12$ rupees $≥ W$ rupees. Thus he can take holiday on the remaining days.

Source: codechef | Difficulty: EASY
Tags: Sorting

Greedy algorithms


Solutions:
goals = int(input())
for i in range(goals):
	(wife, aim) = map(int, input().split())
	life = list(map(int, input().split()))
	life.sort()
	(stress, death) = (0, 0)
	for i in range(wife - 1, -1, -1):
		death += life[i]
		if death >= aim:
			print(len(life) - stress - 1)
			break
		stress += 1
	else:
		print(0)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	(c, d) = (0, 0)
	for i in range(a - 1, -1, -1):
		d += l[i]
		if d >= b:
			print(len(l) - c - 1)
			break
		c += 1
	else:
		print(0)


for _ in range(int(input())):
	(n, w) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	s = 0
	i = n - 1
	while s < w:
		s = s + a[i]
		i = i - 1
	print(i + 1)


for _ in range(int(input())):
	(n, w) = map(int, input().split())
	a = [int(i) for i in input().split()][:n]
	max_money = []
	while True:
		if sum(max_money) >= w:
			break
		max_money.append(a.pop(a.index(max(a))))
	print(n - len(max_money))


for _ in range(int(input())):
	(n, w) = map(int, input().split())
	l = sorted(list(map(int, input().split())))
	c = 0
	for j in range(n - 1, -1, -1):
		c += l[j]
		if c >= w:
			print(j)
			break
	else:
		print(0)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort(reverse=True)
	sm = 0
	idx = 0
	while sm < k:
		sm += arr[idx]
		idx += 1
	print(n - idx)


T = int(input())
for i in range(T):
	(N, W) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort(reverse=True)
	money_earned = A[0]
	days_worked = 1
	for i in range(1, N):
		if money_earned >= W:
			break
		money_earned += A[i]
		days_worked += 1
	print(N - days_worked)


T = int(input())
for i in range(T):
	(N, W) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	B = A[::-1]
	s = 0
	c = 0
	for j in range(N):
		if s < W:
			s += B[j]
			c += 1
	print(N - c)


t = int(input())
for _ in range(t):
	(n, w) = map(int, input().split())
	money = list(map(int, input().split()))
	money.sort()
	ans = 0
	index = -1
	for i in range(n - 1, -1, -1):
		if ans < w:
			ans += money[i]
		else:
			index = i + 1
			break
	if index == -1:
		print(0)
	else:
		print(index)


for i in range(int(input())):
	(n, w) = list(map(int, input().split()))
	m = list(map(int, input().split()))
	m.sort()
	if sum(m) <= w:
		print(0)
	elif sum(m) >= w:
		i = len(m) - 1
		s = 0
		c = 0
		while i >= 0:
			s += m[i]
			c += 1
			if s >= w:
				print(len(m) - c)
				break
			else:
				i -= 1


for _ in range(int(input())):
	(n, w) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	money = l[0]
	c = 1
	for i in range(1, n):
		if money >= w:
			break
		money += l[i]
		c += 1
	print(n - c)


for testcase in range(int(input())):
	(n, w) = map(int, input().split())
	arr = sorted(list(map(int, input().split())))
	total = 0
	for i in range(n - 1, -1, -1):
		total += arr[i]
		if total >= w:
			print(i)
			break
	else:
		print(0)


for _ in range(int(input())):
	(list_length, required) = list(map(int, input().split()))
	day_values = list(map(int, input().split()))
	day_values.sort(reverse=True)
	counter = 0
	so_far = 0
	while so_far < required:
		counter += 1
		so_far += day_values[0]
		day_values.remove(day_values[0])
	print(list_length - counter)


t = int(input())
for i in range(t):
	(n, w) = map(int, input().split())
	data = list(map(int, input().split()))
	data.sort()
	s = 0
	c = 0
	for i in range(n - 1, -1, -1):
		s = s + data[i]
		if s >= w:
			print(i)
			break
	else:
		print(0)


T = int(input())
for t in range(T):
	(N, W) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	A.sort(reverse=True)
	s = 0
	for (k, a) in enumerate(A):
		s += a
		if s >= W:
			print(N - k - 1)
			break


t = int(input())
for _ in range(t):
	(n, w) = map(int, input().split())
	ls = list(map(int, input().split()))
	ls.sort(reverse=True)
	c = 0
	for v in ls:
		if w <= 0:
			break
		w -= v
		c += 1
	print(n - c)


n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	f = sorted(list(map(int, input().split())))
	c = 0
	for j in range(a - 1, -1, -1):
		c += f[j]
		if c >= b:
			print(j)
			break
	else:
		print(0)


t = int(input())
for i in range(t):
	(n, w) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	c = 0
	for j in range(n - 1, -1, -1):
		c += a[j]
		if c >= w:
			print(j)
			break
	else:
		print(0)


t = int(input())
for nt in range(t):
	(n, w) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	count = 0
	a.reverse()
	for i in range(len(a)):
		if count >= w:
			break
		count += a[0]
		a.pop(0)
	print(len(a))


t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	lst = list(map(int, input().split()))
	ans = 0
	lst.sort()
	for j in lst[::-1]:
		if y > 0:
			y -= j
			ans += 1
		else:
			break
	print(len(lst) - ans)


for _ in range(int(input())):
	(x, y) = input().split()
	(x, y) = (int(x), int(y))
	z = list(map(int, input().split()))
	z.sort()
	z = z[::-1]
	k = z[0]
	j = 1
	for i in range(1, x):
		if k >= y:
			break
		k += z[i]
		j += 1
	m = x - j
	if m > 0:
		print(m)
	else:
		print('0')


t = int(input())
for i in range(0, t):
	(n, w) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	sum = 0
	c = 0
	for i in range(n):
		if sum < w:
			sum += a[i]
			c += 1
		else:
			break
	print(n - c)


n = int(input())
for j in range(n):
	s = 0
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	l.reverse()
	for i in range(len(l)):
		s += l[i]
		if s >= b:
			print(len(l) - i - 1)
			break


for i in range(int(input())):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	l = sorted(l)
	c = 0
	d = 0
	l1 = l[::-1]
	for i in l1:
		c += i
		d += 1
		if c >= b:
			print(a - d)
			break


t = int(input())
for _ in range(t):
	(n, w) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	for i in range(n):
		if sum(l[:i + 1]) >= w:
			val = i
			break
	print(n - 1 - val)


t = int(input())
for i in range(t):
	(N, W) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort(reverse=True)
	sum = 0
	for j in range(len(A)):
		sum += A[j]
		if sum >= W:
			break
	print(N - j - 1)


for i in range(int(input())):
	(N, C) = map(int, input().split())
	li = list(map(int, input().split()))
	li = sorted(li)
	i = N - 1
	tot = 0
	while i >= 0:
		tot += li[i]
		i -= 1
		if tot >= C:
			break
	print(i + 1)


test_cases = int(input())
for _ in range(test_cases):
	(N, W) = input().split()
	(N, W) = (int(N), int(W))
	list1 = []
	list1.extend(input().split())
	list2 = sorted([int(x) for x in list1], reverse=True)
	sum = 0
	for (count, j) in enumerate(list2):
		sum += int(j)
		if sum >= W:
			break
	holiday = len(list2) - count - 1
	print(holiday)


for _ in range(0, int(input())):
	(x, y) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	s = 0
	c = 0
	for i in range(x - 1, -1, -1):
		s = s + l[i]
		if s >= y:
			print(i)
			break
	else:
		print(0)


for _ in range(int(input())):
	(n, w) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	k = 0
	while k < w:
		k += a.pop()
	print(len(a))


for x in range(0, int(input())):
	(n, w) = map(int, input().split())
	array = list(map(int, input().split()))
	array = sorted(array, reverse=True)
	sum1 = 0
	count = 0
	for x in range(0, n):
		if sum1 < w:
			sum1 += array[x]
			count += 1
		else:
			break
	print(len(array) - count)


t = int(input())
for _ in range(t):
	(n, w) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	sum = 0
	count = 0
	for each in l:
		sum = sum + each
		count = count + 1
		if sum < w:
			pass
		else:
			break
	print(n - count)


n = int(input())
for i in range(n):
	l = []
	m = []
	(a, b) = map(int, input().split(' '))
	l = sorted([int(i) for i in input().split(' ')], reverse=True)
	for j in range(len(l)):
		m.append(l[j])
		if sum(m) >= b:
			print(a - len(m))
			break


for t in range(int(input())):
	(n, w) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	a.sort(reverse=True)
	money = 0
	i = 0
	while money < w:
		money += a[i]
		i += 1
	print(n - i)


for i in range(int(input())):
	(n, w) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	a = a[::-1]
	summ = 0
	for i in range(len(a)):
		summ += a[i]
		if summ >= w:
			break
	print(n - i - 1)


n = int(input())
for i in range(1, n + 1):
	(x, y) = map(int, input().split())
	z = list(map(int, input().split()))
	t = max(z)
	for j in range(x):
		if t >= y:
			print(x - (j + 1))
			break
		else:
			z.remove(max(z))
			t += max(z)


for _ in range(int(input())):
	(n, w) = map(int, input().split())
	days = sorted(list(map(int, input().split())))
	sumd = 0
	while sumd < w:
		sumd += days.pop()
	print(len(days))


for _ in range(int(input())):
	(n, w) = map(int, input().split())
	days = sorted(list(map(int, input().split())))
	sumd = sum(days)
	if w == sumd:
		print(0)
		continue
	if w <= max(days):
		print(n - 1)
		continue
	sumd = 0
	while sumd < w:
		sumd += days.pop()
	print(len(days))


t = int(input())
for i in range(t):
	(n, w) = map(int, input().split())
	l = list(map(int, input().split()))
	t = 0
	c = 0
	l.sort(reverse=True)
	for i in range(len(l)):
		t += l[i]
		if t >= w:
			print(n - i - 1)
			break


t = int(input())
for tc in range(t):
	(n, w) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	s = 0
	for j in range(n - 1, -1, -1):
		s += a[j]
		if s >= w:
			print(j)
			break
	else:
		print('0')


def solve():
	(n, w) = map(int, input().split())
	l = sorted(list(map(int, input().split())))
	x = 0
	for j in range(n - 1, -1, -1):
		x += l[j]
		if x >= w:
			return j
	return 0
for i in range(int(input())):
	print(solve())


t = int(input())
for i in range(t):
	(list_of_length, req) = list(map(int, input().split()))
	day_values = list(map(int, input().split()))
	day_values.sort(reverse=True)
	count = 0
	dis = 0
	while dis < req:
		count += 1
		dis += day_values[0]
		day_values.remove(day_values[0])
	print(list_of_length - count)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	z = [int(q) for q in input().split()]
	z.sort()
	z.reverse()
	a = 0
	b = []
	for i in range(x):
		if a < y:
			a = a + z[i]
			b.append(z[i])
		else:
			break
	c = len(z) - len(b)
	print(c)


test_cases = int(input())
for i in range(test_cases):
	(n, w) = map(int, input().split())
	arr = list(map(int, input().split()))[:n]
	arr.sort(reverse=True)
	e = 0
	k = 1
	for i in range(n):
		if e >= w:
			print(n - i)
			k = 0
			break
		else:
			e = e + arr[i]
	if k == 1:
		print('0')


t = int(input())
for i in range(t):
	(n, w) = map(int, input().split())
	L = list(map(int, input().strip().split()))
	total = len(L)
	money = 0
	D = []
	while money < w:
		largest = max(L)
		D.append(largest)
		L.remove(largest)
		money = money + largest
	print(total - len(D))


n = int(input())
for i in range(n):
	l = []
	(arr_size, max_amt) = map(int, input().split(' '))
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	j = 0
	suma = 0
	for k in l:
		suma += k
		if suma >= max_amt:
			break
		j += 1
	print(arr_size - j - 1)


for i in range(int(input())):
	(n, w) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	k = l[0]
	count = 1
	for i in range(1, n):
		if k >= w:
			break
		k = k + l[i]
		count += 1
	print(n - count)


t = int(input())
for i in range(t):
	(n, w) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	val = 0
	count = 0
	for j in range(n):
		val += a[j]
		count += 1
		if val >= w:
			break
	print(n - count)


t = int(input())
for _ in range(t):
	(N, W) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	arr1 = sorted(arr)
	arr1 = arr1[::-1]
	money = 0
	days = 0
	for i in range(N):
		money = money + arr1[i]
		if money >= W:
			days = i + 1
			break
	print(N - days)


for _ in range(int(input())):
	(d, m) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	count = 0
	sumval = 0
	for i in range(d - 1, -1, -1):
		if sumval >= m:
			break
		else:
			sumval += l[i]
			count += 1
	print(d - count)


n = int(input())
for i in range(n):
	(n, w) = map(int, input().split(' '))
	arr = [int(x) for x in input().split(' ')]
	arr = sorted(arr, reverse=True)
	sum_earn = 0
	for i in range(n):
		sum_earn += arr[i]
		if sum_earn >= w:
			break
	print(n - i - 1)