Vasya has got many devices that work on electricity. He's got n supply-line filters to plug the devices, the i-th supply-line filter has a_{i} sockets.

Overall Vasya has got m devices and k electrical sockets in his flat, he can plug the devices or supply-line filters directly. Of course, he can plug the supply-line filter to any other supply-line filter. The device (or the supply-line filter) is considered plugged to electricity if it is either plugged to one of k electrical sockets, or if it is plugged to some supply-line filter that is in turn plugged to electricity. 

What minimum number of supply-line filters from the given set will Vasya need to plug all the devices he has to electricity? Note that all devices and supply-line filters take one socket for plugging and that he can use one socket to plug either one device or one supply-line filter.


-----Input-----

The first line contains three integers n, m, k (1 ≤ n, m, k ≤ 50) — the number of supply-line filters, the number of devices and the number of sockets that he can plug to directly, correspondingly. The second line contains n space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 50) — number a_{i} stands for the number of sockets on the i-th supply-line filter.


-----Output-----

Print a single number — the minimum number of supply-line filters that is needed to plug all the devices to electricity. If it is impossible to plug all the devices even using all the supply-line filters, print -1.


-----Examples-----
Input
3 5 3
3 1 2

Output
1

Input
4 7 2
3 3 2 4

Output
2

Input
5 5 1
1 3 1 2 1

Output
-1



-----Note-----

In the first test case he can plug the first supply-line filter directly to electricity. After he plug it, he get 5 (3 on the supply-line filter and 2 remaining sockets for direct plugging) available sockets to plug. Thus, one filter is enough to plug 5 devices.

One of the optimal ways in the second test sample is to plug the second supply-line filter directly and plug the fourth supply-line filter to one of the sockets in the second supply-line filter. Thus, he gets exactly 7 sockets, available to plug: one to plug to the electricity directly, 2 on the second supply-line filter, 4 on the fourth supply-line filter. There's no way he can plug 7 devices if he use one supply-line filter.

Source: codeforces | Difficulty: EASY
Tags: Sorting

Implementation

Greedy algorithms


Solutions:
(n, m, k) = input().split()
n = int(n)
m = int(m)
k = int(k)
a = list(map(int, input().split()))
a = sorted(a, reverse=True)
s = 0
i = 0
f = True
while k + s < m:
	s += a[i] - 1
	i += 1
	if i == n and k + s < m:
		f = False
		break
if m == 1 and k == 1:
	print(0)
elif f:
	print(i)
else:
	print(-1)


(n, m, k) = list(map(int, input().split()))
v = list(map(int, input().split()))
available = 0
v.sort(reverse=True)
ans = -1
if k >= m:
	ans = 0
else:
	for i in range(n):
		if i < k:
			available += v[i]
		else:
			available += v[i] - 1
		if available + max(0, k - i - 1) >= m:
			ans = i + 1
			break
print(ans)


(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
for i in range(n):
	if k >= m:
		print(i)
		i = -2
		break
	k += a[i] - 1
if i == n - 1 and k >= m:
	print(n)
elif k < m:
	print(-1)


(n, m, k) = map(int, input().split())
a = sorted(list(map(int, input().split())))
a.reverse()
t = k
ans = 0
d = False
if t >= m:
	d = True
if not d:
	ans = -1
	for i in range(n):
		t += a[i] - 1
		if t >= m:
			ans = i + 1
			flag = True
			break
print(ans)


def foo():
	(n, m, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	a = sorted(a, reverse=True)
	if m <= k:
		print(0)
		return
	i = 0
	for x in a:
		k += x - 1
		i += 1
		if m <= k:
			print(i)
			return
	print(-1)
foo()


def sockets(n_int, m_int, k_int, filter_sockets_list) -> int:
	if m_int <= k_int:
		return 0
	else:
		sockets_by_filters = m_int - (k_int - 1)
		filter_sockets_list.sort(reverse=True)
		i = 0
		filter_socket_sum = filter_sockets_list[i]
		while filter_socket_sum < sockets_by_filters and i < len(filter_sockets_list) - 1:
			i += 1
			filter_socket_sum += filter_sockets_list[i] - 1
		if filter_socket_sum < sockets_by_filters:
			return -1
		else:
			return i + 1
(n, m, k) = list(map(int, input().split()))
filter_sockets = list(map(int, input().split()))
print(sockets(n, m, k, filter_sockets))


list1 = input()
l = list1.split()
l = [int(item) for item in l]
(n, m, k) = l
a = input()
a1 = map(int, a.split())
a1 = list(sorted(a1))
count = 0
for i in range(len(a1)):
	if k >= m:
		break
	else:
		k += a1.pop() - 1
		count += 1
if k >= m:
	print(count)
else:
	print('-1')


(n, m, k) = map(int, input().split())
flag = False
for (i, a) in enumerate(sorted(map(int, input().split()), reverse=True)):
	if k >= m:
		print(i)
		flag = True
		break
	k += a - 1
if not flag:
	if k >= m:
		print(n)
	else:
		print(-1)


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


(n, m, k) = list(map(int, input().split()))
for (i, a) in enumerate(sorted(map(int, input().split()), reverse=True)):
	if k >= m:
		print(i)
		return
	k += a - 1
if k >= m:
	print(n)
else:
	print(-1)


(a, b, c) = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
p = 0
a -= 1
while a >= 0 and c < b:
	c -= 1
	p += 1
	c += arr[a]
	a -= 1
if c < b:
	print(-1)
else:
	print(p)


(n, m, k) = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
x = x[::-1]
if m <= k:
	print(0)
else:
	d = 0
	f = 1
	for i in x:
		k += i - 1
		d += 1
		if m <= k:
			print(d)
			f = 0
			break
	if f:
		print(-1)


(f, d, s) = [int(i) for i in input().split()]
filters = [int(i) for i in input().split()]
filters.sort(reverse=True)
freeSockets = s
usedFilters = 0
for i in range(len(filters)):
	if freeSockets >= d:
		break
	usedFilters += 1
	freeSockets += filters[i] - 1
if freeSockets >= d:
	print(usedFilters)
else:
	print(-1)


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


class CodeforcesTask257ASolution:

	def __init__(self):
		self.result = ''
		self.n_m_k = []
		self.filters = []

	def read_input(self):
		self.n_m_k = [int(x) for x in input().split(' ')]
		self.filters = [int(x) for x in input().split(' ')]

	def process_task(self):
		self.filters.sort(reverse=True)
		needed = 0
		if self.n_m_k[1] - self.n_m_k[2]:
			undirect = self.n_m_k[1] + 1 - self.n_m_k[2]
		else:
			undirect = 0
		if undirect > 0:
			undirect -= 1
			for supply_filter in self.filters:
				needed += 1
				undirect -= supply_filter - 1
				if undirect <= 0:
					break
		if undirect > 0:
			self.result = '-1'
		else:
			self.result = str(needed)

	def get_result(self):
		return self.result
Solution = CodeforcesTask257ASolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


3
(n, m, k) = tuple(map(int, input().split()))
a = reversed(sorted(map(int, input().split())))
ans = 0
for _ in a:
	if m <= k:
		break
	ans += 1
	m -= k - 1
	k = _
print(ans if m <= k else -1)


import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__
(n, m, k) = map(int, input().split())
filters = list(map(int, input().split()))
filters.sort()
supply_filters_needed = 0
if k < m:
	spots = k
	end = n - 1
	while spots < m and end >= 0:
		spots += filters[end] - 1
		supply_filters_needed += 1
		end -= 1
	if spots < m:
		print(-1)
	else:
		print(supply_filters_needed)
else:
	print(0)


def main():
	(n, m, k) = map(int, input().split())
	socets = sorted(list(map(int, input().split())), reverse=True)
	ans = 0
	for i in socets:
		if m <= k:
			print(ans)
			return
		else:
			k = k + i - 1
			ans += 1
			if m <= k:
				print(ans)
				return
	print(-1)
main()


I = lambda : map(int, input().split())
(n, m, k) = I()
m -= k
x = 0
for (i, a) in enumerate(sorted(I(), reverse=True)):
	if m <= 0:
		print(i)
		break
	m -= a - 1
else:
	print(-1 if m > 0 else n)


def main():
	[n, m, k] = [int(x) for x in input().split()]
	l = [int(x) for x in input().split()]
	print(result(n, m, k, l))

def result(n, m, k, l):
	f = 0
	l.sort()
	l.reverse()
	while k < m:
		if l == []:
			return -1
		f += 1
		k += l[0] - 1
		l = l[1:]
	return f
main()


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


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


(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
a = [val for val in a if val > 1]
a.sort(reverse=True)
out_cnt = k
l = 0
while l <= len(a):
	if out_cnt >= m:
		print(l)
		break
	elif l == len(a):
		print('-1')
		break
	else:
		out_cnt += a[l] - 1
		l += 1


(n, m, k) = map(int, input().split())
arr = [int(i) for i in input().split()]
(i, res) = (0, 0)
arr = sorted(arr, reverse=True)
while i < n and k < m:
	k += arr[i] - 1
	res += 1
	i += 1
print(-1 if k < m else res)


def socket(n, m, k, arr):
	arr.sort(reverse=True)
	devices = m
	curr_socket = 0
	e_socket = k
	i = 0
	t_socket = 0
	count = 0
	while i < n:
		if e_socket >= devices:
			return 0
		if curr_socket == 0:
			curr_socket += arr[i]
			count += 1
			e_socket -= 1
			t_socket = curr_socket + e_socket
		elif t_socket >= devices:
			return count
		else:
			curr_socket += arr[i] - 1
			count += 1
			t_socket = curr_socket + e_socket
		i += 1
	if t_socket >= devices:
		return count
	return -1
(n, m, k) = map(int, input().split())
arr = list(map(int, input().split()))
print(socket(n, m, k, arr))


(n_extnson, n_dvics, n_sokts) = list(map(int, input().split()))
extensions = list(map(int, input().split()))
extensions.sort(reverse=True)
devices_left = n_dvics - n_sokts
extnson_used = 0
i = 0
while devices_left > 0 and n_extnson > 0:
	devices_left += 1
	extnson_siez = extensions[i]
	devices_left -= extnson_siez
	extnson_used += 1
	n_extnson -= 1
	i += 1
if devices_left > 0:
	print(-1)
else:
	print(extnson_used)


def main():
	(n, m, k) = map(int, input().split())
	m -= k
	if m > 0:
		for (i, a) in enumerate(sorted(map(int, input().split()), reverse=True), 1):
			m -= a - 1
			if m <= 0:
				print(i)
				break
		else:
			print(-1)
	else:
		print(0)
main()


(n, m, k) = input().split()
n = int(n)
m = int(m)
k = int(k)
l = list(map(int, input().split()))
l.sort()
l.reverse()
z = k
f = 0
while z < m and f < n:
	z += l[f] - 1
	f += 1
if z >= m:
	print(f)
else:
	print(-1)


[n, m, k] = input().split()
n = int(n)
m = int(m)
k = int(k)
data = [int(i) for i in input().split()]
ans = 0
for i in reversed(sorted(data)):
	if k < m:
		k += int(i) - 1
		ans += 1
	else:
		break
if k < m:
	ans = -1
print(ans)


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


read = lambda : map(int, input().split())
(n, m, k) = read()
a = sorted(read())
s = sum(a)
if m <= k:
	print(0)
elif k + s - n < m:
	print(-1)
else:
	t = k
	result = 0
	for i in range(n - 1, -1, -1):
		t += a[i] - 1
		result += 1
		if t >= m:
			break
	print(result)


(n, m, k) = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
arr = arr + [k]
ans = 0
s = 0
while ans < n + 1:
	s += arr[-ans - 1]
	if s >= m:
		break
	ans += 1
	s -= 1
if s >= m:
	print(ans)
else:
	print('-1')


(n, m, k) = map(int, input().split())
x = [int(q) for q in input().split()]
x = sorted(x)
x = x[::-1]
i = 0
while k < m and i < n:
	k += x[i] - 1
	i += 1
if i <= n and k >= m:
	print(i)
else:
	print(-1)


def main():
	(n, m, k) = list(map(int, input().split(' ')))
	a = list(reversed(sorted(list(map(int, input().split(' '))))))
	ret = 0
	i = 0
	if k >= m:
		return 0
	while i < n:
		ret += 1
		k += a[i] - 1
		if k >= m:
			return ret
		i += 1
	if k < m:
		return -1
	return ret
print(main())


(n, m, k) = list(map(int, input().split()))
a = sorted(list(map(int, input().split())), reverse=True)
c = 0
while k < m and c < n:
	k += a[c] - 1
	c += 1
if c >= 0 and k >= m:
	print(c)
else:
	print(-1)


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


import sys
(n, m, k) = tuple((int(s) for s in sys.stdin.readline().split(' ')))
filters = [int(a) for a in sys.stdin.readline().split(' ')]
if m <= k:
	print(0)
	sys.exit()
count = 0
filters.sort(reverse=True)
for f in filters:
	k = k + f - 1
	count = count + 1
	if m <= k:
		print(count)
		sys.exit()
else:
	print(-1)


import sys
input = sys.stdin.readline
I = lambda : map(int, input().split())
(n, m, k) = I()
l = list(I())
l.sort(reverse=True)
count = 0
if k >= m:
	count = 0
else:
	for i in range(n):
		count += 1
		k += l[i] - 1
		if k >= m:
			break
		if (k == 0 or l[i] == 1) or k == 0:
			count = -1
			break
	if k < m:
		count = -1
print(count)


(n, m, k) = list(map(int, input().rstrip().split()))
a = list(map(int, input().rstrip().split()))
a.sort(reverse=True)
if m <= k:
	print(0)
else:
	ans = 0
	x = m
	while True:
		maxm = a.pop(0)
		m = m - maxm
		k = k - 1
		ans += 1
		if k >= m:
			print(ans)
			break
		elif ans == n:
			print(-1)
			break


(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
s = 0
count = 0
i = 0
while k < m and i < n:
	k += a[i] - 1
	i += 1
print(i if k >= m else -1)


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


from sys import stdin
aux = list(map(int, stdin.readline().split()))
n = aux[0]
m = aux[1]
k = aux[2]
arr = list(map(int, stdin.readline().split()))
arr.sort(reverse=True)
ans = 0
if m <= k:
	m = 0
else:
	m -= k - 1
for x in arr:
	if m <= 0:
		break
	ans += 1
	m -= x - 1
	if m == 1:
		m = 0
if m <= 0:
	print(ans)
else:
	print(-1)


import sys
import math
(n, m, k) = [int(x) for x in sys.stdin.readline().split()]
an = [int(x) for x in sys.stdin.readline().split()]
an.sort(reverse=True)
res = 0
i = 0
while m > k:
	if i < n:
		k -= 1
		k += an[i]
		i += 1
	else:
		break
	res += 1
if m <= k:
	print(res)
else:
	print(-1)


import sys
import math
from sys import stdin, stdout

def sieve(N):
	primeNumbers = [True] * (N + 1)
	primeNumbers[0] = False
	primeNumbers[1] = False
	i = 2
	while i * i <= N:
		j = i
		if primeNumbers[j]:
			while j * i <= N:
				primeNumbers[j * i] = False
				j += 1
		i += 1
	return primeNumbers

def getPrime(N):
	primes = sieve(N)
	result = []
	for i in range(len(primes)):
		if primes[i]:
			result.append(i)
	return result

def factor(N):
	factors = []
	i = 1
	while i * i <= N:
		if N % i == 0:
			factors.append(i)
			if i != N // i:
				factors.append(N // i)
		i += 1
	return sorted(factors)

def reduceB(b):
	mod = 0
	for i in range(0, len(b)):
		mod = (mod * 10 + ord(b[i])) % 1000000007
	return mod

def gcd(a, b):
	if a < b:
		return gcd(b, a)
	if b == 0:
		return a
	return gcd(b, a % b)

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

def get_int():
	return int(input())

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

def get_list_of_list(n):
	return [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]

def get_string():
	return sys.stdin.readline().strip()

def main():
	(filters, devices, sockets) = get_ints_in_variables()
	socket = get_ints_in_list()
	socket.sort(reverse=True)
	if devices <= sockets:
		print(0)
	elif devices > sockets:
		start = 0
		reaminingDevices = devices
		remainingSockets = sockets
		remainingFilters = filters
		while start < len(socket) and reaminingDevices > remainingSockets:
			remainingFilters -= 1
			reaminingDevices -= socket[start]
			remainingSockets -= 1
			start += 1
		if reaminingDevices <= remainingSockets:
			diff = filters - remainingFilters
			print(diff)
			return
		else:
			print(-1)
			return
main()


import os
import sys
from math import *
from collections import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
(n, m, k) = value()
a = sorted(array(), reverse=True)
a.insert(0, k)
for i in range(n + 1):
	if m <= a[i]:
		m -= a[i]
		break
	m -= a[i] - 1
if m > 0 or k == 0:
	print(-1)
else:
	print(i)


(n, m, k) = map(int, input().split())
l = list(map(int, input().split()))
l = sorted(l, reverse=True)
socket = k
plugs = 0
i = 0
while socket + plugs < m and i < n and (socket >= 0):
	if socket > 0:
		socket = socket - 1
		plugs += l[i]
	else:
		plugs += l[i] - 1
	i += 1
if plugs + socket < m or socket < 0:
	print('-1')
else:
	print(i)


def solve():
	(n, m, k) = map(int, input().split())
	l = sorted(list(map(int, input().split())), reverse=True)
	m -= k
	for i in range(n):
		if m <= 0:
			return i
		m -= l[i] - 1
	return -1 if m > 0 else n
print(solve())


(n, m, k) = map(int, input().split())
a = sorted(map(int, input().split()))
r = [x for x in range(n + 1) if sum(a[n - x:]) + k >= m + x]
print(min(r) if r else -1)


(n, m, k) = [int(x) for x in input().split(' ')]
a = [int(x) for x in input(' ').split(' ')]
a.sort(reverse=True)
if m <= k:
	print(0)
else:
	u = 0
	for r in a:
		u += 1
		k += r - 1
		if m <= k:
			break
	if m <= k:
		print(u)
	else:
		print(-1)


(n, m, k) = map(int, input().split())
(*l,) = sorted(map(int, input().split()), reverse=True)
if k >= m:
	print(0)
else:
	i = 0
	s = k
	while i < n and s < m:
		s += l[i] - 1
		i += 1
	if s < m:
		print(-1)
	else:
		print(i)


(n, m, k) = [int(y) for y in input().split()]
a = [int(y) for y in input().split()]
a.sort(reverse=True)
no = 0
while k < m and no < n:
	k += a[no] - 1
	no += 1
if k < m:
	print(-1)
else:
	print(no)


from sys import stdin
import functools
import math

def read():
	return map(int, stdin.readline().split())
(_, dev, sockets) = read()
dev -= sockets
a = sorted(list(read()))
ans = 0
while dev > 0 and len(a) > 0:
	dev -= a.pop() - 1
	ans += 1
if dev > 0:
	print('-1')
else:
	print(ans)


(n, m, k) = (int(x) for x in input().split())
a = [int(x) for x in input().split()]
a.sort()
a.reverse()
if k >= m:
	print(0)
	return
for (i, x) in enumerate(a):
	k += x - 1
	if k >= m:
		print(i + 1)
		return
print(-1)


(n, m, k) = map(int, input().split())
t = list(map(int, input().split()))
t.sort()
g = [1] * k
f = 0
(l, h) = (0, 0)
if sum(g) >= m:
	print(0)
else:
	for j in range(n - 1, -1, -1):
		if j == n - 1:
			g[-1] = t[j]
		else:
			g[-1] += t[j] - 1
		l += 1
		if sum(g) >= m:
			print(l)
			h += 1
			break
	if h == 0:
		print(-1)


(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
num = 0
ans = -1
while m > k:
	if num > n - 1:
		num = -1
		break
	num += 1
	k += a[num - 1] - 1
print(num)


(n, m, k) = map(int, input().split())
sp = sorted(map(int, input().split()))
socket_count = 0
sp_count = 0
sc = 0
if k >= m:
	print(0)
	exit()
for i in range(n):
	if k > 0:
		n -= 1
		k -= 1
		sp_count += 1
		sc = sc + sp.pop()
		socket_count = sc + k
		if socket_count >= m:
			print(sp_count)
			exit()
	else:
		n -= 1
		sp_count += 1
		socket_count -= 1
		socket_count = socket_count + sp.pop()
		if socket_count >= m:
			print(sp_count)
			exit()
print(-1)


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


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


(n, m, k) = map(int, input().split())
filters = list(map(int, input().split()))
filters.sort(reverse=True)
ans = 0
if m <= k:
	print(ans)
else:
	left = m
	i = 0
	done = False
	while i < n:
		ans += 1
		if left <= filters[i] + (k - 1):
			print(ans)
			done = True
			break
		else:
			left -= filters[i] - 1
			i += 1
	if not done:
		print(-1)


(n, m, k) = map(int, input().split())
s = sorted(list(map(int, input().split())), reverse=True)
s.append(1)
i = 0
while i <= n:
	if k >= m:
		print(i)
		exit(0)
	else:
		k += s[i] - 1
		i += 1
print(-1)


from sys import stdin, stdout
ii1 = lambda : int(stdin.readline())
is1 = lambda : stdin.readline()
iia = lambda : map(int, stdin.readline().split())
isa = lambda : stdin.readline().split()
(n, m, k) = iia()
arr = sorted(iia(), reverse=True)
count = 0
for i in arr:
	if m <= k:
		print(count)
		break
	elif m - i <= 0 and k > 0:
		print(count + 1)
		break
	else:
		count += 1
		m -= i
		k -= 1
else:
	if m <= 0 and k > 0:
		print(count)
	else:
		print(-1)


(n, m, k) = list(map(int, input().split()))
l = list(map(int, input().split()))
l.sort(reverse=True)
if m <= k:
	print(0)
	quit()
for (ii, c) in enumerate(l):
	k += c - 1
	if k >= m:
		print('{}'.format(ii + 1))
		quit()
print(-1)


(x, y, z) = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
c = 0
s = z
t = False
while s < y and c < x:
	c += 1
	s = s + l[x - c] - 1
if s < y:
	print(-1)
else:
	print(c)


(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
a = a[::-1]
if m <= k:
	print(0)
else:
	c = 0
	while c < n:
		k = k + a[c] - 1
		c += 1
		if k >= m:
			print(c)
			exit()
	else:
		print(-1)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=-10 ** 6, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=10 ** 6, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(50001)]
pp = []

def SieveOfEratosthenes(n=50000):
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for i in range(50001):
		if prime[i]:
			pp.append(i)
(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
if k >= m:
	print(0)
else:
	curr = k
	count = 0
	for i in range(n):
		curr += a[i] - 1
		count += 1
		if curr >= m:
			break
	if curr >= m:
		print(count)
	else:
		print(-1)


s = input().split()
n = int(s[0])
m = int(s[1])
k = int(s[2])
a = []
mp = map(int, input().split())
for j in mp:
	a.append(j)
a.sort(reverse=True)
if k >= m:
	print(0)
else:
	ans = -1
	count = 0
	total = 0
	sum = 0
	for j in range(n):
		count += 1
		sum += a[j]
		total = k - count + sum
		if total >= m:
			break
	if total >= m:
		ans = count
	print(ans)


def met(n, m, k, a):
	a.sort(reverse=True)
	if k >= m:
		return 0
	for (i, e) in enumerate(a):
		if k + e - 1 >= m:
			return i + 1
		if e == 1:
			return -1
		k += e - 1
	return -1
(n, m, k) = tuple(map(int, input().split(' ')))
a = list(map(int, input().split(' ')))
print(met(n, m, k, a))


import sys
import math
import itertools
import collections

def divs(n, start=2):
	r = []
	for i in range(start, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n / i == i:
				r.append(i)
			else:
				r.extend([i, n // i])
	return r

def cdiv(n, k):
	return n // k + (n % k != 0)

def ii():
	return int(input())

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

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

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def wr(arr):
	return ' '.join(map(str, arr))

def revn(n):
	return str(n)[::-1]

def prime(n):
	if n == 2:
		return True
	if n % 2 == 0 or n <= 1:
		return False
	sqr = int(math.sqrt(n)) + 1
	for d in range(3, sqr, 2):
		if n % d == 0:
			return False
	return True

def convn(number, base=3):
	newnumber = ''
	while number > 0:
		newnumber = str(number % base) + newnumber
		number //= base
	return newnumber
(n, m, k) = mi()
x = sorted(li(), reverse=True)
i = 0
if sum(x) + k - n + 1 <= m:
	print(-1)
else:
	ans = 0
	while m > k:
		k += x[i] - 1
		i += 1
		ans += 1
	print(ans)


(n, m, k) = map(int, input().split())
ext = [int(k) for k in input().split()]
ext.sort(reverse=True)
paso = True
tomas = 0
while m > k:
	try:
		k += ext[tomas] - 1
		tomas += 1
	except:
		paso = False
		break
if paso:
	print(tomas)
else:
	print(-1)


(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
sum1 = k
if k >= m:
	print(0)
	exit()
i = 0
while i < n and sum1 < m:
	sum1 += a[i] - 1
	i += 1
if sum1 >= m:
	print(i)
else:
	print(-1)


(n, m, k) = map(int, input().split())
l1 = list(map(int, input().split()))
if sum(l1) - n + k < m:
	print(-1)
else:
	l1.sort()
	l1 = l1[::-1]
	i = 0
	while k < m:
		k += l1[i] - 1
		i += 1
	print(i)


(n, m, k) = map(int, input().split())
a = [int(x) for x in input().split()]
a = sorted(a, reverse=True)
minNum = min(a)
if k >= m:
	print(0)
else:
	if k != 1:
		m = m - k + 1
	else:
		m = m
	c = 0
	i = 0
	while i < n and m > 0:
		if a[i] == m:
			m = m - a[i]
			c += 1
		elif a[i] >= m:
			c += 1
			m = 0
			break
		elif m - a[i] + 1 >= minNum:
			m = m - a[i] + 1
			c += 1
		i = i + 1
	if m != 0:
		print(-1)
	else:
		print(c)


(n, m, k) = map(int, input().split())
list = sorted(list(map(int, input().split())))
list.reverse()
temp = 0
ans = 0
count = 0
for i in list:
	ans += i
	if k >= m:
		temp = 1
		break
	count += 1
	if k > 0:
		z = ans + k - 1
		k = k - 1
	if k == 0:
		ans = 0
		k = z
	if z >= m:
		temp = 1
		break
if temp == 1:
	print(count)
else:
	print(-1)


(n, m, k) = map(int, input().split())
f = list(map(int, input().split()))
f.sort()
ans = 0
if k < m:
	spots = k
	end = n - 1
	while spots < m and end >= 0:
		spots += f[end] - 1
		ans += 1
		end -= 1
	if spots < m:
		print(-1)
	else:
		print(ans)
else:
	print(0)


import sys
from math import *
input = sys.stdin.readline
RI = lambda : [int(x) for x in sys.stdin.readline().strip().split()]
rw = lambda : input().strip().split()
ls = lambda : list(input().strip())
from collections import defaultdict as df
import heapq
infinite = float('inf')
(n, m, k) = RI()
l = RI()
l.sort(reverse=True)
if m <= k:
	print(0)
else:
	extra = m - k
	i = 0
	ans = 0
	while extra > 0 and i < n:
		extra -= l[i] - 1
		ans += 1
		i += 1
	if extra <= 0:
		print(ans)
	else:
		print(-1)


(n, m, k) = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
c = 0
devices = k
i = 0
while devices < m and i < n:
	c += 1
	devices += a[i] - 1
	i += 1
if devices < m:
	print(-1)
else:
	print(c)


nmk = list(map(int, input().strip().split()))
n = nmk[0]
m = nmk[1]
k = nmk[2]
lst = list(map(int, input().strip().split()))
lst.sort(reverse=True)
i = 0
while k < m and i < n:
	k = k + lst[i] - 1
	i += 1
if i <= n and k >= m:
	print(i)
else:
	print(-1)


(n, m, k) = map(int, input().split())
l = list(map(int, input().split()))
l.sort(reverse=True)
s = k
c = 0
while s < m and n > c:
	s = s + l[c] - 1
	c = c + 1
if s >= m:
	print(c)
else:
	print('-1')


ino = list(map(int, input().split()))
inos = list(map(int, input().split()))
n = ino[0]
m = ino[1]
k = ino[2]
del ino
flag = False
for i in range(len(inos)):
	for j in range(len(inos) - 1, i, -1):
		if inos[j] > inos[j - 1]:
			(inos[j], inos[j - 1]) = (inos[j - 1], inos[j])
if m <= k:
	print(0)
	flag = True
else:
	m = m - (k - 1)
	j = 0
	while m > 0:
		if j != 0:
			m += 1
		m = m - inos[j]
		if j + 1 == n and m != 0:
			print(-1)
			flag = True
			break
		j += 1
if flag == False:
	print(j)


(n, m, k) = map(int, input().split())
l = list(map(int, input().split()))
l.sort(reverse=True)
if m < k:
	print('0')
else:
	c = k
	i = 0
	j = 0
	flag = 0
	while c < m:
		if i == n:
			flag = 1
			break
		c = c - 1
		c = c + l[i]
		i = i + 1
		j = j + 1
	if flag == 1:
		print('-1')
	else:
		print(j)


(f, u, r) = map(int, input().split())
fr = list(sorted(map(int, input().split()), reverse=True))
k = 0
while k < f and r < u:
	r += fr[k] - 1
	k += 1
print(-1 if r < u else k)


temp = list(map(int, input().split()))
l = list(map(int, input().split()))
l.sort(reverse=True)
s = 0
k = temp[2]
k = k - 1
m = temp[1]
ans = temp[0] + 2
for i in range(0, temp[0]):
	s = s + l[i]
	if s + k >= m:
		ans = i + 1
		break
	s = s - 1
if temp[2] >= m:
	print(0)
elif ans > temp[0]:
	print(-1)
else:
	print(ans)


import math
import os
import random
import re
import sys
import functools
from operator import itemgetter, attrgetter
(n, m, k) = list(map(int, input().strip().split()))
(a, b, i) = (list(map(int, input().strip().split())), 0, 0)
a.sort(reverse=True)
if m <= k:
	print(b)
else:
	while i < len(a):
		if m <= k:
			break
		if k > 0:
			k -= 1
		elif m > 0:
			m += 1
		m -= a[i]
		b += 1
		i += 1
	print('-1' if m > k else '{}'.format(b))


(n, m, k) = map(int, input().split())
lis = list(map(int, input().split()))
lis = list(map(lambda x: x - 1, lis))
lis.sort()
dev = 0
while k < m and len(lis) > 0:
	k = k + lis[-1]
	lis.pop(-1)
	dev = dev + 1
if k < m:
	print(-1)
else:
	print(dev)


from bisect import bisect_left
(n, m, k) = tuple(map(int, input().split()))
a = sorted(map(int, input().split()), reverse=True)
s = [k] + [0] * n
for i in range(n):
	s[i + 1] = s[i] + a[i] - 1
ans = bisect_left(s, m)
print(ans if ans <= n else -1)


(n, m, k) = map(int, input().split())
l = list(map(int, input().split()))
l = sorted(l)
ava = k
i = n - 1
ans = 0
result = False
while i >= 0:
	if ava >= m:
		result = True
		break
	ava += l[i] - 1
	i -= 1
	ans += 1
if ava >= m:
	result = True
if result:
	print(ans)
else:
	print(-1)


(n, m, k) = map(int, input().split())
t = list(map(int, input().split()))
t.sort(reverse=True)
m -= k
i = 0
if m > 0:
	while i < n:
		m -= t[i] - 1
		i += 1
		if m <= 0:
			break
print(i if m <= 0 else -1)


(n, m, k) = list(map(int, input().split()))
f = list(map(int, input().split()))
f.sort()
fs = 0
ptr = len(f) - 1
while ptr >= 0:
	if m <= k:
		print(fs)
		exit()
	k -= 1
	k += f[ptr]
	fs += 1
	ptr -= 1
if m <= k:
	print(fs)
else:
	print(-1)


try:
	(n, m, k) = map(int, input().split())
	w = list(map(int, input().split()))
	w.sort()
	w = w[::-1]
	ans = 0
	while k < m and ans < n:
		k += w[ans] - 1
		ans += 1
	if k >= m:
		print(ans)
	else:
		print(-1)
except:
	pass


(a, b, c) = map(int, input().split())
l = [int(i) for i in input().split()]
if b <= c:
	print(0)
else:
	l.sort(reverse=True)
	d = 0
	f = 1
	for i in l:
		c += i - 1
		d += 1
		if b <= c:
			print(d)
			f = 0
			break
	if f == 1:
		print(-1)


(n, m, k) = map(int, input().split())
ns = list(map(lambda x: int(x), input().split()))
ns.sort()
ns.reverse()
if m <= k:
	print(0)
else:
	m = m - k + 1
	i = 0
	while i < len(ns):
		m -= ns[i]
		if m < 1:
			print(i + 1)
			break
		i += 1
		m += 1
	else:
		print(-1)


(n, m, k) = map(int, input().split(' '))
li = list(map(int, input().split(' ', n)[:n]))
li.sort(reverse=True)
fl = 0
(a, s) = (0, 0)
if m <= k:
	print(0)
else:
	while fl == 0 and a < n:
		s += li[a]
		a += 1
		if a != 1:
			s -= 1
		if s + k - 1 >= m and a != 0:
			fl = 1
			break
	if fl != 1:
		print(-1)
	else:
		print(a)