Ivan has $n$ songs on his phone. The size of the $i$-th song is $a_i$ bytes. Ivan also has a flash drive which can hold at most $m$ bytes in total. Initially, his flash drive is empty.

Ivan wants to copy all $n$ songs to the flash drive. He can compress the songs. If he compresses the $i$-th song, the size of the $i$-th song reduces from $a_i$ to $b_i$ bytes ($b_i < a_i$).

Ivan can compress any subset of the songs (possibly empty) and copy all the songs to his flash drive if the sum of their sizes is at most $m$. He can compress any subset of the songs (not necessarily contiguous).

Ivan wants to find the minimum number of songs he needs to compress in such a way that all his songs fit on the drive (i.e. the sum of their sizes is less than or equal to $m$).

If it is impossible to copy all the songs (even if Ivan compresses all the songs), print "-1". Otherwise print the minimum number of songs Ivan needs to compress.


-----Input-----

The first line of the input contains two integers $n$ and $m$ ($1 \le n \le 10^5, 1 \le m \le 10^9$) — the number of the songs on Ivan's phone and the capacity of Ivan's flash drive.

The next $n$ lines contain two integers each: the $i$-th line contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le 10^9$, $a_i > b_i$) — the initial size of the $i$-th song and the size of the $i$-th song after compression.


-----Output-----

If it is impossible to compress a subset of the songs in such a way that all songs fit on the flash drive, print "-1". Otherwise print the minimum number of the songs to compress.


-----Examples-----
Input
4 21
10 8
7 4
3 1
5 4

Output
2

Input
4 16
10 8
7 4
3 1
5 4

Output
-1



-----Note-----

In the first example Ivan can compress the first and the third songs so after these moves the sum of sizes will be equal to $8 + 7 + 1 + 5 = 21 \le 21$. Also Ivan can compress the first and the second songs, then the sum of sizes will be equal $8 + 4 + 3 + 5 = 20 \le 21$. Note that compressing any single song is not sufficient to copy all the songs on the flash drive (for example, after compressing the second song the sum of sizes will be equal to $10 + 4 + 3 + 5 = 22 > 21$).

In the second example even if Ivan compresses all the songs the sum of sizes will be equal $8 + 4 + 1 + 4 = 17 > 16$.

Difficulty: introductory

Starter code:

Solutions:
#      
import collections, atexit, math, sys
from functools import cmp_to_key
#key=cmp_to_key(lambda x,y: 1 if x not in y else -1 )

sys.setrecursionlimit(1000000)
def getIntList():
    return list(map(int, input().split()))    

import bisect 
try :
    #raise ModuleNotFoundError
    import numpy
    def dprint(*args, **kwargs):
        print(*args, **kwargs, file=sys.stderr)
    dprint('debug mode')
except ModuleNotFoundError:
    def dprint(*args, **kwargs):
        pass


def memo(func):  
    cache={}  
    def wrap(*args):  
        if args not in cache:  
            cache[args]=func(*args)  
        return cache[args]  
    return wrap

@memo
def comb (n,k):
    if k==0: return 1
    if n==k: return 1
    return comb(n-1,k-1) + comb(n-1,k)

inId = 0
outId = 0
if inId>0:
    dprint('use input', inId)
    sys.stdin = open('input'+ str(inId) + '.txt', 'r') #标准输出重定向至文件
if outId>0:
    dprint('use output', outId)
    sys.stdout = open('stdout'+ str(outId) + '.txt', 'w') #标准输出重定向至文件
    atexit.register(lambda :sys.stdout.close())     #idle 中不会执行 atexit
    
N, M = getIntList()
total = 0
zz = [0 for i in range(N)]
for i in range(N):
    a,b = getIntList()
    total+=a
    zz[i] = a-b

zz.sort(reverse = True)
if total <= M:
    print(0)
    return
for i in range(N):
    total -= zz[i]
    if total <= M:
        print(i+1)
        return

print(-1)





n, m = list(map(int, input().split()))
sum_a = 0
sum_b = 0
arr = []
for i in range(n):
    a, b = list(map(int, input().split()))
    sum_a += a
    sum_b += b
    arr.append(a - b)
if sum_a <= m:
    print(0)
elif sum_b > m:
    print(-1)
else:
    arr.sort(reverse=True)
    ans = 0
    i = 0
    while sum_a > m:
        ans += 1
        sum_a -= arr[i]
        i += 1
    print(ans)


n, m = [int(i) for i in input().split()]
diff = []
s = 0
for i in range(n):
    a, b = [int(j) for j in input().split()]
    diff.append(a - b)
    s += a
diff.sort()
ans = 0
for i in reversed(range(n)):
    if s <= m:
        break
    s -= diff[i]
    ans += 1
if s <= m:
    print(ans)
else:
    print(-1)

def go():
    n, m = [int(i) for i in input().split(' ')]
    s_a = 0
    s_b = 0
    c = []
    for i in range(n):
        data = [int(i) for i in input().split(' ')]
        s_a += data[0]
        s_b += data[1]
        c.append(data[0] - data[1])
    if s_b > m:
        return -1

    x = s_a
    i = 0
    c = list(sorted(c, reverse=True))
    while x > m:
        x -= c[i]
        i += 1

    return i

print(go())


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


n,m=list(map(int,input().split()))
s=[]
s1=[]
for i in range(n):
    a,b=list(map(int,input().split()))
    s.append(a)
    s1.append(a-b)
x=sum(s)
s1.sort()
ans=0
while x>m and len(s1)>0:
    ans+=1
    x-=s1[-1]
    s1.pop()
if x>m:
    print(-1)
else:
    print(ans)


n,money=map(int,input().split())
ans=[]
for _ in range(n):
    a,b=map(int,input().split())
    ans.append([a,b,a-b])
s=0
for i in range(len(ans)):
    s=s+ans[i][0]
m=[]
for i in range(len(ans)):
    m.append(ans[i][2])
m.sort(reverse=True)
if s<=money:
    print(0)
elif s-sum(m)>money:
    print(-1)
else:
    c=0
    for i in range(len(m)):
        c+=1
        s=s-m[i]
        if s<=money:
            break
    print(c)

n, m = list(map(int,input().split()))
a = []
s = 0
for i in range(n):
    k, b = list(map(int,input().split()))
    s += k
    a.append(k - b)
a.sort(reverse=True)
ans = 0
for i in range(n):
    if s <= m:
        print(ans)
        return
    s -= a[i]
    ans += 1
if s <= m:
    print(ans)
else:
    print(-1)


nbMusiques, taille = map(int, input().split())
tableau = []
somme = 0

for i in range(nbMusiques):
   avant, apres = map(int, input().split())
   somme += avant
   tableau.append(avant-apres)

tableau.sort()

if somme <= taille:
   print(0)

else:
   for i in range(nbMusiques):
      somme -= tableau[nbMusiques-1-i]
   
      if somme <= taille:
         print(i+1)
         break
   
   if somme > taille:
      print(-1)

n, m = map(int, input().split())
inf = 0
szhat = [0]*n
for i in range(n):
    a, b = map(int,input().split())
    inf += a
    szhat[i] = (a-b)
szhat.sort()
p = [0] * (n+1)
for i in range(1, n+1):
    p[i] = p[i-1] + szhat[-i]
if inf - p[n] > m:
    print(-1)
else:
    L, R = -1, n
    while R - L > 1:
        med = (R+L)//2
        if inf - p[med] > m:
            L = med
        else:
            R = med
    print(R)

n, m = map(int, input().split())
a = []
b = []
for i in range(n):
    x, y = map(int, input().split())
    a.append(x)
    b.append(y)
if sum(b) > m:
    print(-1)
else:
    c = [a[i] - b[i] for i in range(len(a))]
    c.sort()
    s = sum(b)
    res = 0
    for i in c:
        if s + i <= m:
            res += 1
            s += i
        else:
            break
    print(n - res)

n,size=map(int,input().split())
li=[]
for _ in range(n):
    a,b=map(int,input().split())
    li.append((a,b,a-b))
sum=0;sum1=0
for i in range(n):
    sum+=li[i][1]
    sum1+=li[i][0]
if sum>size:
    print(-1)
    return
if(sum1<=size):
    print(0)
    return
li.sort(key=lambda x:x[2],reverse=True)
dif=sum1-size
count=0
for i in range(n):
    if dif<=0:
        break
    dif-=li[i][2]
    count+=1
print(count)

n,size=map(int,input().split())
pot=list()
tot=0
for i in range(n):
    a,b=map(int,input().split())
    pot.append(a-b)
    tot+=a
pot.sort()
pot=pot[::-1]
cpt=0
while(tot>size and cpt<len(pot)):
    tot-=pot[cpt]
    cpt+=1
if(tot>size):print(-1)
else:print(cpt)

n, m = list(map(int, input().split()))

a = []
b = []

non_compressed = 0
compressed = 0
saves = []

for i in range(n):
    ai, bi = list(map(int, input().split()))
    non_compressed += ai
    compressed += bi
    saves.append(ai - bi)

if ( compressed > m ):
    print(-1)
else:
    saves.sort(reverse=True)
    z = 0
    while ( non_compressed > m ):
        non_compressed -= saves[z]
        z = z + 1
    print(z)


n, m = list(map(int, input().split()))
sumb = 0
suma = 0
s = []
sumschat = 0
k = 0
for i in range(n):
    a, b = list(map(int, input().split()))
    s.append(a - b)
    sumb = sumb + b
    suma = suma + a
if sumb > m:
    print(-1)
else:
    i = 0
    s.sort(reverse = True)
    while sumschat < suma - m:
        sumschat = sumschat + s[i]
        i = i + 1
        k = k + 1
    print(k)


import sys

n, m = map(int, sys.stdin.readline().split())
song = [None]*n
somme = 0
for loop in range(n):
    d, f = map(int, sys.stdin.readline().split())
    somme += d
    song[loop] = d-f
song.sort(reverse=True)
total = 0
while total < n and somme > m:
    somme-= song[total]
    total += 1
if somme > m:
    print(-1)
else:
    print(total)

cnt, memory = list(map(int, input().split()))
deltas = [0] * cnt
musics = []
curr_memory = 0
for ind in range(cnt):
    full, small = list(map(int, input().split()))
    musics.append([full, small])
    curr_memory += full
    deltas[ind] = full - small

deltas.sort()
count_changes = 0
steps = 0
while curr_memory > memory and steps < cnt:
    curr_memory -= deltas[cnt - steps - 1]
    steps += 1

if curr_memory <= memory:
    print(steps)
else:
    print(-1)


n, m = list(map(int, input().split()))
d = []
nsum = 0
for _ in range(n):
    a, b = list(map(int, input().split()))
    d.append(a-b)
    nsum += a
d.sort(reverse = True)
ans = 0
for i in range(n):
    if nsum <= m:
        print(ans)
        return
    else:
        nsum -= d[i]
        ans += 1
print(-1 if nsum > m else ans)


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


# from math import ceil
#from sys import stdout

t = 1#int(input())
for test in range(1,t+1):
    n,m = list(map(int, input().split()))
    a = 0
    b = 0
    c = []
    for i in range(n):
        l,r = list(map(int, input().split()))
        a+=l
        b+=r
        c.append(l-r)
    if b>m:
        print(-1)
    else:
        c.sort(reverse = True)
        diff = a-m
        ans = 0
        ind = 0
        while diff>0:
            diff -= c[ind]
            ind+=1
            ans+=1
        print(ans)











    


n, m  = list(map(int, input().split()))

po = []
ps = []
diffs = []

for i in range(n):
    a, b =  list(map(int, input().split()))
    po.append(a)
    ps.append(b)
    diffs.append(a-b)
tlen  = sum(po)
tslen = sum(ps)

diffs.sort(reverse = True)

if sum(po) <= m:
    print(0)
    return
if sum(ps) > m:
    print(-1)
    return

r = sum(po)
cnt = 0
for d in diffs:
    cnt += 1
    r -= d
    if r<=m:
        print(cnt)
        return





import sys
s=input().split()
n=int(s[0])
m=int(s[1])
siz=0
dec=[None]*n
for i in range(n):
    s=input().split()
    siz+=int(s[0])
    dec[i]=int(s[1])-int(s[0])
dec.sort()
if siz<=m:
    print(0)
    return
for i in range(n):
    siz+=dec[i]
    if siz<=m:
        print(i+1)
        return
print(-1)

n, m = [int(x) for x in str(input()).split(' ', 1)]
a = []
b = []
d = []
for _ in range(n):
    lx, rx = [int(x) for x in str(input()).split(' ', 1)]
    a.append(lx)
    b.append(rx)
    d.append(lx - rx)
if sum(b) > m:
    print(-1)
    return
if sum(a) <= m:
    print(0)
    return
s = sum(a)
for i, v in enumerate(sorted(d, reverse=True)):
    s -= v
    if s <= m:
        print(i + 1)
        break

from sys import stdin,stdout

def main():
   n,m=list(map(int,stdin.readline().split()))
   A=[0 for _ in range(n)]
   B=[0 for _ in range(n)]
   
   for i in range(n):
      A[i],B[i]=list(map(int,stdin.readline().split()))
   
   tot=sum(A)
   C=[A[i]-B[i] for i in range(n)]
   C.sort()
   
   i=0
   while i<n and tot>m:
      i+=1
      tot-=C[-i]
   
   if tot<=m:
       stdout.write('{}'.format(i))
   else:
      stdout.write("-1")

main()



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

n,m = mi()
diff = [0]*n
s1 = 0
s2 = 0
for i in range(n):
	n1, n2 = mi()
	s1+=n1
	s2+=n2
	diff[i] = n1-n2
diff.sort()
if s2>m:
	print (-1)
else:
	diff.sort(reverse=True)
	c = 0
	for i in diff:	
		if s1<=m:
			break
		s1-=i
		c+=1
	print (c)