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.

Difficulty: interview

Starter code:

Solutions:
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)


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)

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
        #print('i='+str(i)+' t='+str(t)+' result='+str(result))
        if t>=m:
            break
    print(result)

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    
def __starting_point():
    main()

__starting_point()

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)


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)


n, m, k = 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
print(n if k >= m else -1)

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)



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)
	return

count = 0
filters.sort(reverse=True)

for f in filters:
	k = k + f - 1
	count = count + 1
	if m <= k:
		print(count)
		return
else:
	print(-1)


s = input().split()
n = int(s[0])
m = int(s[1])
k = int(s[2])
a = []
mp = list(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 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 main():
    n, m, k = list(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)


def __starting_point():
    main()

__starting_point()

n, m, k = list(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)


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
#a = 1
for i in range(len(inos)):
        for j in range(len(inos) - 1, i, -1):
            #print(i)
            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)

"""
    while flag == False:
        for i in range(len(inos)):
            m = m - len(inos) + a - inos[a-1]

#for i in range(len(inos)):
#    print(inos[i])

#print(str(ino[0]), str(ino[1]), str(ino[2]))
"""

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 = [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)

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


n,m,k = list(map(int, input().split()))
#lst = 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)


n, m, k = list(map(int,input().split()))
line = [int(x) for x in input().split()]
line.sort(reverse = True)
count = 0
if k >=m:
    print(count)
    return
for i in range(n):
    k += line[i]-1
    count += 1
    if k >= m:
        print(count)
        return
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] = 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)

from sys import stdin
import functools
import math

def read(): return list(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)
  


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)

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