Andrew likes meatballs very much.
He has N plates of meatballs, here the i^{th} plate contains P_{i} meatballs. You need to find the minimal number of plates Andrew needs to take to his trip to Las Vegas, if he wants to eat there at least M meatballs. Note that each plate is already packed, i.e. he cannot change the amount of meatballs on any plate.

------ Input ------ 

The first line of the input contains an integer T, denoting the number of test cases. The description of T test cases follows. The first line of each test case contains two space-separated integers N and M. The second line contains N space-separated integers P_{1}, P_{2}, ..., P_{N}.

------ Output ------ 

For each test case, output an integer, denoting the minimum number of plates. If it's impossible to take at least M meatballs, print -1.

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

$1 ≤ T ≤ 7777$
$1 ≤ N ≤ 7$
$1 ≤ M, P_{i} ≤ 10^{18}$

----- Sample Input 1 ------ 
1
4 7
1 2 3 4
----- Sample Output 1 ------ 
2
----- explanation 1 ------ 
If he takes 3rd and 4th plates, then we may eat P3 + P4 = 7 meatballs in Las Vegas. This is the only way for eating at least M = 7 meatballs with 2 plates.

Difficulty: EASY
Tags: Sorting

Constructive algorithms

Data structures

Ad-hoc
Skill types: Sorting

Data structures

Starter code:

Solutions:
import math as ma
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	s = sum(l)
	l.sort()
	k = -1
	while s >= m:
		l.pop(0)
		s = sum(l)
		k += 1
	if n - k > n:
		print('-1')
	else:
		print(n - k)


def solve(N, M, a):
	a.sort()
	if sum(a) < M:
		return -1
	else:
		count = 1
		sums = a[N - 1]
		for i in range(1, N + 1):
			if sums >= M:
				return count
			else:
				sums = sums + a[N - 1 - i]
				count += 1
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	a = list(map(int, input().split()))
	print(solve(N, M, a))


def sum(lst):
	s = 0
	for i in lst:
		s = s + i
	return s
b = int(input())
for i in range(b):
	c = list(map(int, input().split()))
	a = list(map(int, input().split()))
	a.sort()
	s = sum(a)
	k = -1
	while s >= c[1]:
		a.pop(0)
		s = sum(a)
		k = k + 1
	if c[0] - k > c[0]:
		print(-1)
	else:
		print(c[0] - k)


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


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


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	arr = []
	arr = list(map(int, input().split()))
	arr.sort()
	total = 0
	count = 0
	while len(arr) > 0 and total < m:
		total += arr[-1]
		count += 1
		arr.pop()
	if total >= m:
		print(count)
	else:
		print(-1)


t = int(input())
for tc in range(t):
	(n, l) = map(int, input().split())
	p = list(map(int, input().split()))
	p.sort()
	a = p[::-1]
	s = 0
	c = []
	for j in a:
		if l > 0:
			l -= j
			s += 1
		elif l <= 0:
			break
	if l > 0:
		s = -1
	print(s)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr = sorted(arr)
	arr = arr[::-1]
	ans = 0
	for i in range(len(arr)):
		if b > 0:
			b = b - arr[i]
			ans += 1
		elif b <= 0:
			break
	if b > 0:
		ans = -1
	print(ans)


T = int(input())
for i in range(T):
	(N, M) = map(int, input().split())
	P = sorted(list(map(int, input().strip().split())))
	P.reverse()
	sum = 0
	c = 0
	for j in range(len(P)):
		if sum >= M:
			break
		else:
			sum += P[j]
			c += 1
	if sum >= M:
		print(c)
	else:
		print(-1)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	l = sorted(list(map(int, input().split())))
	l.reverse()
	sum = 0
	count = 0
	for i in range(n):
		if sum >= x:
			break
		else:
			sum += l[i]
			count += 1
	if sum >= x:
		print(count)
	else:
		print(-1)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	x = list(map(int, input().split()))
	x.sort(reverse=True)
	ans = 0
	for i in range(len(x)):
		if b > 0:
			b = b - x[i]
			ans += 1
		elif b <= 0:
			break
	if b > 0:
		ans = -1
	print(ans)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	L = list(map(int, input().split()))
	sum1 = 0
	sum2 = 0
	L.sort(reverse=True)
	for item in L:
		sum1 = sum1 + item
		sum2 = sum2 + 1
		if sum1 >= m:
			print(sum2)
			break
	if sum1 < m:
		print(-1)
	else:
		continue


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	L = sorted(map(int, input().split()), reverse=True)
	s = cnt = 0
	while s < M and cnt < len(L):
		s += L[cnt]
		cnt += 1
	print(cnt if s >= M else -1)


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


for tc in range(int(input())):
	(N, M) = map(int, input().split())
	P = list(map(int, input().split()))
	P.sort(reverse=True)
	maxsum = 0
	count = 0
	for i in range(N):
		maxsum += P[i]
		count += 1
		if maxsum >= M:
			break
	if maxsum >= M:
		print(count)
	else:
		print(-1)


q = int(input())
while q > 0:
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	w = 0
	c = 0
	flag = 0
	for i in l:
		w = w + i
		c = c + 1
		if w >= m:
			flag = 1
			print(c)
			break
	if flag == 0:
		print(-1)
	q = q - 1


for i in range(int(input())):
	(n, m) = map(int, input().split())
	p = sorted(list(map(int, input().split())), reverse=True)
	e = 0
	i = 0
	y = 0
	for x in p:
		e = e + x
		i = i + 1
		if e >= m:
			y = 1
			print(i)
			break
	if y == 0:
		print(-1)


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


t = int(input())
for u in range(t):
	(n, m) = map(int, input().split())
	p = list(map(int, input().split()))
	p.sort()
	p.reverse()
	s = 0
	c = 0
	f = 0
	for i in p:
		s += i
		c += 1
		if s >= m:
			f = 1
			break
	if f == 0:
		print(-1)
	else:
		print(c)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = sorted([int(x) for x in input().split()], reverse=True)
	ans = 0
	cur = 0
	if sum(a) < k:
		ans = -1
	else:
		for i in a:
			cur += i
			ans += 1
			if cur >= k:
				break
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	p = list(sorted(map(int, input().split())))
	s = 0
	flag = True
	for i in range(n - 1, -1, -1):
		s += p[i]
		if s >= m:
			flag = False
			print(n - i)
			break
	if flag:
		print(-1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	lst = list(map(int, input().split()))
	lst.sort(reverse=True)
	s = 0
	cnt = 0
	for i in lst:
		s = s + i
		cnt += 1
		if s >= k:
			print(cnt)
			s = 0
			break
	if s != 0:
		print(-1)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split(' '))
	l = sorted(list(map(int, input().split(' '))))
	s = 0
	count = 0
	for i in range(n - 1, -1, -1):
		s = s + l[i]
		count += 1
		if s >= m:
			print(count)
			break
	if s < m:
		print(-1)


t = int(input())
while t != 0:
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort(reverse=True)
	sp = 0
	for i in range(0, n):
		sp += arr[i]
		if sp >= m:
			print(i + 1)
			break
	if sp < m:
		print(-1)
	t -= 1


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	n_list = list(map(int, input().split()))
	n_list.sort(reverse=True)
	plate = 0
	meatballs = 0
	for i in n_list:
		plate += 1
		meatballs += i
		if meatballs >= m:
			print(plate)
			break
	if m > meatballs:
		print(-1)


for _ in range(int(input())):
	(n, m) = map(int, input().split(' '))
	p = sorted(list(map(int, input().split(' '))))
	plates = 0
	meatballs = 0
	for i in range(1, n + 1):
		if meatballs >= m:
			break
		meatballs += p[-i]
		plates += 1
	print(-1 if meatballs < m else plates)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	p = [int(i) for i in input().split()]
	p.sort(reverse=True)
	c = 0
	ind = 0
	for i in p:
		c = c + i
		ind = ind + 1
		if c >= m:
			print(ind)
			break
	if c < m:
		print(-1)


from collections import Counter
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	c = 0
	f = 0
	ind = 0
	for i in l:
		c += i
		ind += 1
		if c >= m:
			f = 1
			break
	if f == 1:
		print(ind)
	else:
		print(-1)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	x = list(map(int, input().split()))
	sum = 0
	i = 0
	h = 0
	for g in range(a):
		h += x[g]
	if b > h:
		print(-1)
	elif b == h:
		print(a)
	elif b == 0:
		print(0)
	else:
		while len(x) > 0:
			sum += max(x)
			x.remove(max(x))
			i += 1
			if sum >= b:
				print(i)
				break


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


def balls(p, n, m):
	s = 0
	d = 0
	for i in range(n):
		s += p[i]
		d += 1
		if s >= m:
			print(d)
			break
	else:
		print(-1)
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	p = list(map(int, input().split()))
	p.sort(reverse=True)
	balls(p, n, m)


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


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = sorted(list(map(int, input().split())), reverse=True)
	total = 0
	num = 0
	for i in arr:
		if total >= m:
			break
		num += 1
		total += i
	if total >= m:
		print(num)
	else:
		print(-1)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	p = sorted(map(int, input().split()))[::-1]
	ans = 0
	som = 0
	for i in p:
		som += i
		ans += 1
		if som >= m:
			break
	if som >= m:
		print(ans)
	else:
		print(-1)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	p = list(map(int, input().split()))
	maxsum = 0
	count = 0
	p.sort(reverse=True)
	for i in range(n):
		maxsum += p[i]
		count += 1
		if maxsum >= m:
			break
	if maxsum >= m:
		print(count)
	else:
		print(-1)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	c = 0
	if m > sum(l):
		print(-1)
	else:
		while m > 0:
			m -= l[-1]
			del l[-1]
			c = c + 1
		print(c)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	lst = list(map(int, input().split()))
	lst.sort()
	lst = lst[::-1]
	if m > sum(lst):
		print(-1)
		continue
	c = 0
	for i in lst:
		if m > 0:
			m -= i
			c += 1
		else:
			break
	print(c)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	p = list(map(int, input().split()))
	p.sort()
	if sum(p) < m:
		print(-1)
	else:
		c = 0
		while m > 0:
			m -= p[-1]
			del p[-1]
			c += 1
		print(c)


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


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


for i in range(int(input())):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	(c, d, e) = (0, 0, 0)
	lst = []
	if sum(arr) < m:
		d = -1
	else:
		while True:
			c = max(arr)
			e += 1
			lst.append(c)
			arr.remove(c)
			if sum(lst) >= m:
				d = e
				break
	print(d)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	ls = list(map(int, input().split()))
	ls.sort(reverse=True)
	amount = 0
	counter = 0
	for i in range(n):
		amount += ls[i]
		counter += 1
		if amount >= x:
			break
	print(-1 if amount < x else counter)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	(c, d, e) = (0, 0, 0)
	l = []
	if sum(a) < m:
		d = -1
	else:
		while True:
			c = max(a)
			e += 1
			l.append(c)
			a.remove(c)
			if sum(l) >= m:
				d = e
				break
	print(d)


for i in range(int(input())):
	(N, M) = map(int, input().split())
	P = list(map(int, input().split()))
	P.sort()
	P.reverse()
	b = 0
	a = 0
	if sum(P) >= M:
		for j in P:
			a = a + j
			b = b + 1
			if M <= a:
				print(b)
				break
	else:
		print(-1)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	x = 0
	y = 0
	for i in l:
		x += i
		y += 1
		if x >= k:
			break
	if x < k:
		print(-1)
	else:
		print(y)


testcase = int(input())
for i in range(testcase):
	(n, m) = map(int, input().split())
	lst = list(map(int, input().split()))
	lst.sort(reverse=True)
	num = 0
	plates = 0
	done = 0
	for j in range(0, n):
		plates += 1
		num += lst[j]
		if num >= m:
			done = 1
			break
	if done == 1:
		print(plates)
	else:
		print('-1')


t = int(input())

def solucion(n, m):
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	suma = 0
	for i in range(len(l)):
		suma += l[i]
		if suma >= m:
			return i + 1
	return -1
for _ in range(t):
	(n, m) = map(int, input().split())
	print(solucion(n, m))


t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	p = list(map(int, input().split()))
	p.sort()
	p1 = p[::-1]
	sm = 0
	lis = []
	for i in range(len(p1)):
		sm += p1[i]
		if sm <= m:
			lis.append(p1[i])
		elif sm > m and sm - p1[i] < m:
			lis.append(p1[i])
		else:
			break
	if m > sum(p1):
		print(-1)
	else:
		print(len(lis))


for i in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	l.reverse()
	sum = 0
	c = 0
	for i in l:
		if sum < m:
			sum = sum + i
			c = c + 1
		else:
			break
	if sum < m:
		print('-1')
	else:
		print(c)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	p = list(map(int, input().split()))
	if sum(p) < m:
		print(-1)
	else:
		acc = 0
		i = 0
		p.sort(reverse=True)
		while acc < m:
			acc += p[i]
			i += 1
		print(i)


for t in range(int(input())):
	(a, b) = map(int, input().split())
	p = list(map(int, input().split()))
	t = 0
	an = -1
	p.sort(reverse=True)
	for i in range(a):
		t += p[i]
		if t >= b:
			an = i + 1
			break
	print(an)


t = int(input())
for i in range(t):
	n = list(map(int, input().split(' ')))
	l = list(map(int, input().split(' ')))
	l.sort()
	(s, count) = (0, 0)
	flag = True
	for k in range(n[0] - 1, -1, -1):
		s += l[k]
		count += 1
		if s >= n[1]:
			print(count)
			flag = False
			break
	if flag:
		if s < n[1]:
			print(-1)
		else:
			print(count)


for tc in range(int(input())):
	(n, m) = map(int, input().split())
	p = list(map(int, input().split()))
	tot = 0
	ans = -1
	p.sort(reverse=True)
	for i in range(n):
		tot += p[i]
		if tot >= m:
			ans = i + 1
			break
	print(ans)


t = int(input())
while t > 0:
	t -= 1
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	cur = 0
	cnt = 0
	for x in a:
		cur += x
		cnt += 1
		if cur >= m:
			break
	if cur < m:
		print(-1)
	else:
		print(cnt)


a = int(input(''))
for i in range(a):
	(N, M) = [int(x) for x in input('').split()]
	t = [int(x) for x in input('').split()]
	k = list(t)
	k.sort(reverse=True)
	c = 0
	d = 0
	for j in k:
		c = c + j
		d = d + 1
		if c >= M:
			print(d)
			break
	else:
		print(-1)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	(c, count, m1) = (0, 0, 0)
	l1 = []
	if m > sum(l):
		c = -1
	else:
		while True:
			m1 = max(l)
			count += 1
			l1.append(m1)
			l.remove(m1)
			if sum(l1) >= m:
				c = count
				break
	print(c)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	p = list(map(int, input().split()))
	p.sort()
	p = p[::-1]
	c = 0
	for i in range(len(p)):
		c += p[i]
		if c >= m:
			print(1 + i)
			break
	if c < m:
		print('-1')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	(summ, c, flag) = (0, 0, 0)
	for i in range(n - 1, -1, -1):
		summ += arr[i]
		c += 1
		if summ >= m:
			flag = 1
			break
	if flag == 1:
		print(c)
	else:
		print(-1)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	lst = list(map(int, input().split()))
	sum = 0
	count = 0
	lst.sort(reverse=True)
	for i in lst:
		if sum < m:
			sum += i
			count += 1
		else:
			break
	if sum < m:
		print(-1)
	else:
		print(count)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	p = list(map(int, input().split()))
	p.sort()
	p.reverse()
	sum = 0
	count = 0
	for i in range(n):
		if sum < m:
			sum = sum + p[i]
			count += 1
		else:
			break
	if sum < m:
		print(-1)
	else:
		print(count)


t = int(input())
while t > 0:
	(plates, req) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	(k, flag) = (0, 0)
	for i in range(plates):
		k += l[i]
		if k >= req:
			print(i + 1)
			flag = 1
			break
	if flag == 0:
		print(-1)
	t -= 1


for i in range(int(input())):
	(n, m) = map(int, input().split())
	p = list(map(int, input().split()))
	p = sorted(p, reverse=True)
	summ = 0
	for j in range(n):
		summ += p[j]
		if summ >= m:
			print(j + 1)
			break
	else:
		print(-1)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	a = sorted(a, reverse=True)
	s = 0
	for i in range(n):
		s += a[i]
		if s >= m:
			print(i + 1)
			break
	else:
		print(-1)