The only difference between easy and hard versions is that you should complete all the projects in easy version but this is not necessary in hard version.

Polycarp is a very famous freelancer. His current rating is $r$ units.

Some very rich customers asked him to complete some projects for their companies. To complete the $i$-th project, Polycarp needs to have at least $a_i$ units of rating; after he completes this project, his rating will change by $b_i$ (his rating will increase or decrease by $b_i$) ($b_i$ can be positive or negative). Polycarp's rating should not fall below zero because then people won't trust such a low rated freelancer.

Is it possible to complete all the projects? Formally, write a program to check if such an order of the projects exists, that Polycarp has enough rating before starting each project, and he has non-negative rating after completing each project.

In other words, you have to check that there exists such an order of projects in which Polycarp will complete them, so he has enough rating before starting each project, and has non-negative rating after completing each project.


-----Input-----

The first line of the input contains two integers $n$ and $r$ ($1 \le n \le 100, 1 \le r \le 30000$) — the number of projects and the initial rating of Polycarp, respectively.

The next $n$ lines contain projects, one per line. The $i$-th project is represented as a pair of integers $a_i$ and $b_i$ ($1 \le a_i \le 30000$, $-300 \le b_i \le 300$) — the rating required to complete the $i$-th project and the rating change after the project completion.


-----Output-----

Print "YES" or "NO".


-----Examples-----
Input
3 4
4 6
10 -2
8 -1

Output
YES

Input
3 5
4 -5
4 -2
1 3

Output
YES

Input
4 4
5 2
5 -3
2 1
4 -2

Output
YES

Input
3 10
10 0
10 -10
30 0

Output
NO



-----Note-----

In the first example, the possible order is: $1, 2, 3$.

In the second example, the possible order is: $2, 3, 1$.

In the third example, the possible order is: $3, 1, 4, 2$.

Difficulty: introductory

Starter code:

Solutions:
def sign(x):
    return (x > 0) - (x < 0)


def key(ab):
    a, b = ab
    return (2, -a - b) if b < 0 else (1, a)


def main():
    n, r = list(map(int, input().split()))
    for a, b in sorted((tuple(map(int, input().split())) for _ in range(n)), key=key):
        if r < a:
            r = -1
            break
        r += b
    if r < 0:
        print("NO")
    else:
        print("YES")


main()


n, r = map(int, input().split())

pt = []
nt = []
r2 = r
for _ in range(n):
    a, b = map(int, input().split())
    r2 += b
    if b >= 0:
        pt.append((a, b))
    else:
        nt.append((a, b))

if r2 < 0:
    print('NO')
    return

pt.sort()
nt.sort(key=lambda t: t[0]+t[1])

for a, b in pt:
    if r<a:
        print("NO")
        return
    r += b

for a, b in nt:
    if r2 < a+b:
        print('NO')
        return
    r2 -= b

print('YES')

n, r = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
pos = []
neg = []
for x in a:
    if x[1] > 0:
        pos.append(x)
    else:
        neg.append(x)
pos.sort(key=lambda k: k[0])
flg = 1
for x in pos:
    if r < x[0]:
        flg = 0
    else:
        r += x[1]
neg.sort(key=lambda k: k[0]+k[1], reverse=True)
for x in neg:
    if r < x[0]:
        flg = 0
    else:
        r += x[1]
        if r < 0:
            flg = 0
if flg == 1:
    print('YES')
else:
    print('NO')

n, r = [int(i) for i in input().split()]

proj = [[0 for i in range(2)] for j in range(n)]
posb = 0
sum_neg = 0

for i in range(n):
    proj[i][0], proj[i][1] = [int(j) for j in input().split()]
    if proj[i][1] >= 0: posb += 1
    else: sum_neg += proj[i][1]
        
negb = n-posb
        
proj = sorted(proj, key = lambda elem: elem[1])

proj_pos = sorted(proj[negb:], key = lambda elem: elem[0])

res = True

i = 0

while res and i < posb:
    if r < proj_pos[i][0]: res = False
    else:
        r += proj_pos[i][1]
        i += 1
        
if res:
    proj_neg = sorted(proj[:negb], key = lambda elem: elem[0]+elem[1], reverse = True)
    
    i = 0
    
    while res and i < negb and r >= 0:
        if r < proj_neg[i][0]: res = False
        else:
            r += proj_neg[i][1]
            i += 1
    
    if r >= 0 and res: print("YES")
    else: print("NO")
    
    
else: print("NO")


n,r = map(int, input().split())
aa = [0]*n
bb = [0]*n
for i in range(n):
    aa[i], bb[i] = map(int, input().split())
avail = set(range(n))
fr = r + sum(bb)
if fr < 0:
    print("NO")
    return
ok = True
for i in range(n):
    nxt = -1
    for j in avail:
        if aa[j] <= r and bb[j] >= 0:
            nxt = j
            break
    if nxt == -1:
        break
    avail.remove(nxt)
    r += bb[nxt]
for i in range(len(avail)):
    nxt = -1
    for j in avail:
        if aa[j]+bb[j] <= fr and bb[j] < 0:
            nxt = j
            break
    if nxt == -1:
        ok = False
        break
    avail.remove(nxt)
    fr -= bb[nxt]
if ok:
    print("YES")
else:
    print("NO")

'''input
5 20
45 -6
34 -15
10 34
1 27
40 -45


'''
import sys
from collections import defaultdict as dd

mod=10**9+7

def ri(flag=0):
	if flag==0:
		return [int(i) for i in sys.stdin.readline().split()]
	else:
		return int(sys.stdin.readline())


n, r = ri()

eventspos = []
eventsneg = []
for i in range(n):
	temp =ri()
	if temp[1]>=0:
		eventspos.append(temp)
	else:
		eventsneg.append(temp)

eventspos.sort()
eventsneg.sort(key = lambda x: x[0]+x[1])
eventsneg.reverse()

status =1

ans=0 

for i in range(len(eventspos)):
	if eventspos[i][0] <= r:
		r+= eventspos[i][1]
		ans+=1
	else:
		status = 0


check = [0 for i in range(r+1)]

#print(eventsneg)

for i in range(len(eventsneg)):
	for j in range(eventsneg[i][0] , r+1):
		if j+eventsneg[i][1]>=0:
			check[j+eventsneg[i][1]] = max(check[j+eventsneg[i][1]] , check[j]+1) 



if max(check)+ ans  == n:
	print("YES")
else:
	print("NO")

#print(eventsneg,eventspos)



n, r = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
pos = []
neg = []
for x in a:
    if x[1] > 0:
        pos.append(x)
    else:
        neg.append(x)
pos.sort(key=lambda k: k[0])
flg = 1
for x in pos:
    if r < x[0]:
        flg = 0
    else:
        r += x[1]
neg.sort(key=lambda k: k[0]+k[1], reverse=True)
for x in neg:
    if r < x[0]:
        flg = 0
    else:
        r += x[1]
        if r < 0:
            flg = 0
if flg == 1:
    print('YES')
else:
    print('NO')

import sys
from collections import defaultdict as dd
 
mod=10**9+7
 
def ri(flag=0):
	if flag==0:
		return [int(i) for i in sys.stdin.readline().split()]
	else:
		return int(sys.stdin.readline())
 
 
n, r = ri()
 
eventspos = []
eventsneg = []
for i in range(n):
	temp =ri()
	if temp[1]>=0:
		eventspos.append(temp)
	else:
		eventsneg.append(temp)
 
eventspos.sort()
eventsneg.sort(key = lambda x: x[0]+x[1])
eventsneg.reverse()
 
status =1
 
ans=0 
 
for i in range(len(eventspos)):
	if eventspos[i][0] <= r:
		r+= eventspos[i][1]
		ans+=1
	else:
		status = 0
 
 
check = [0 for i in range(r+1)]
 
#print(eventsneg)
 
for i in range(len(eventsneg)):
	for j in range(eventsneg[i][0] , r+1):
		if j+eventsneg[i][1]>=0:
			check[j+eventsneg[i][1]] = max(check[j+eventsneg[i][1]] , check[j]+1) 
 
 
 
if max(check)+ ans  == n:
	print("YES")
else:
	print("NO")
 
#print(eventsneg,eventspos)


# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
from sys import stdin, stdout
import math

#T = int(input())
#N = int(input())
#print(N)
N,r = [int(x) for x in stdin.readline().split()]
#arr = [int(x) for x in stdin.readline().split()]

visited = [0]*N

a = [0]*N
b = [0]*N

pos = 0

for i in range(N):
    arr = [int(x) for x in stdin.readline().split()]
    a[i] = arr[0]
    b[i] = arr[1]
    
    if b[i]>=0:
        pos += 1

for i in range(pos):
    idx = -1
    start = 0
    gain = -50000
    for j in range(N):
        # find available and largest gain
        # if gain tie, find largest start r
        if visited[j]==1 or b[j]<0:
            continue
            
        if b[j]>gain and r>=a[j]:
            gain = b[j]
            idx = j
            start = a[j]
        elif b[j]==gain and r>=a[j]:
            if a[j]>start:
                idx = j
                start = a[j]
                
    if idx==-1:
        print('NO')
        quit()
    else:
        visited[idx] = 1
        r += b[idx]
        #print(idx,r)
        
        
tmp = []
for i in range(N):
    if visited[i]==1 or b[i]>=0:
        continue
    tmp.append((a[i],b[i],i))
    
tmp.sort(key=lambda e: (e[0]+e[1],e[0]),reverse=True)

for i in range(len(tmp)):
    require = tmp[i][0]
    bias = tmp[i][1]
    
    if r>=require:
        r += bias
    else:
        print('NO')
        quit()
        

if r<0:
    print('NO')
    quit()
        
print('YES')

n, r = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
pos = []
neg = []
for x in a:
    if x[1] > 0:
        pos.append(x)
    else:
        neg.append(x)
pos.sort(key=lambda k: k[0])
flg = 1
for x in pos:
    if r < x[0]:
        flg = 0
    else:
        r += x[1]
neg.sort(key=lambda k: k[0]+k[1], reverse=True)
for x in neg:
    if r < x[0] or r<0:
        flg = 0
    else:
        r += x[1]
if flg == 1 and r>=0:
    print('YES')
else:
    print('NO')

n, r = map(int, input().split())
 
pt = []
nt = []
r2 = r
for _ in range(n):
    a, b = map(int, input().split())
    r2 += b
    if b >= 0:
        pt.append((a, b))
    else:
        nt.append((a, b))
 
if r2 < 0:
    print('NO')
    return
 
pt.sort()
nt.sort(key=lambda t: t[0]+t[1])
 
for a, b in pt:
    if r<a:
        print("NO")
        return
    r += b
 
for a, b in nt:
    if r2 < a+b:
        print('NO')
        return
    r2 -= b
 
print('YES')

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

plus=[]
minn=[]

for i in range (0,n):

    temp = list(map(int,input().split()))

    if temp[1] <=0:
        temp.append(temp[0]+temp[1])
        minn.append(temp)
    else:
        plus.append(temp)

plus.sort()
minn.sort(reverse=True,key = lambda x: x[2])
flag = True
for i in plus:

    if i[0] <= r:
        r+= i[1]
        #print(r)
    else:
        flag=False
        break
#print("GANTI")
if flag:
    for i in minn:
        if i[0] <= r:
            r +=i[1]
            #print(r)
        else:
            flag=False
            break


if flag and r>=0:
    print("YES")
else:
    print("NO")


n,r=list(map(int,input().split()))
arr1=[]
arr2=[]
for i in range(n):
	x,y=list(map(int,input().split()))
	if(y>=0):
		arr1.append((x,y))
	else:
		arr2.append((x,y))
 
arr1.sort()
arr2.sort(reverse=True)
currval=r
flag=0
for i in range(len(arr1)):
	#print(arr1[i][0],currval)
	if(arr1[i][0]>currval):
		print("NO")
		return
	else:
		currval+=arr1[i][1]
tempval=currval
 
mark=[0]*len(arr2)
countx=0
finalans=0
while(countx<len(arr2)):
	flag=-1
	for i in range(len(arr2)):
		if(mark[i]==0 and currval>=arr2[i][0]):
			tempflag=0
			for j in range(len(arr2)):
				if(j!=i and mark[j]==0):
					if(currval+arr2[i][1]<arr2[j][0]):
						tempflag=1
						break
			#print(tempflag)
			if(tempflag==0):
				flag=i
				break
	if(flag==-1):
		finalans=1
		break
	else:
		currval+=arr2[flag][1]
		mark[flag]=1
		countx+=1
if(currval<0):
	finalans=1
if(finalans==0):
	print("YES")
else:
	mark=[0]*len(arr2)
	countx=0
	finalans=0
	currval=tempval
	while(countx<len(arr2)):
		flag=-1
		for i in range(len(arr2)):
			if(mark[i]==0 and currval>=arr2[i][0]):
				tempflag=0
				for j in range(len(arr2)):
					if(j!=i and mark[j]==0):
						if(currval+arr2[i][1]<arr2[j][0]):
							tempflag=1
							break
				#print(tempflag)
				if(tempflag==0):
					flag=i
					
		if(flag==-1):
			print("NO")
			return
			break
		else:
			currval+=arr2[flag][1]
			mark[flag]=1
			countx+=1
	if(currval<0):
		print("NO")
	else:
		print("YES")



n,r=list(map(int,input().split()))
arr1=[]
arr2=[]
for i in range(n):
	x,y=list(map(int,input().split()))
	if(y>=0):
		arr1.append((x,y))
	else:
		arr2.append((x,y))
 
arr1.sort()
arr2.sort(reverse=True)
currval=r
flag=0
for i in range(len(arr1)):
	#print(arr1[i][0],currval)
	if(arr1[i][0]>currval):
		print("NO")
		return
	else:
		currval+=arr1[i][1]
tempval=currval
 
mark=[0]*len(arr2)
countx=0
finalans=0
while(countx<len(arr2)):
	flag=-1
	for i in range(len(arr2)):
		if(mark[i]==0 and currval>=arr2[i][0]):
			tempflag=0
			for j in range(len(arr2)):
				if(j!=i and mark[j]==0):
					if(currval+arr2[i][1]<arr2[j][0]):
						tempflag=1
						break
			#print(tempflag)
			if(tempflag==0):
				flag=i
				break
	if(flag==-1):
		finalans=1
		break
	else:
		currval+=arr2[flag][1]
		mark[flag]=1
		countx+=1
if(currval<0):
	finalans=1
if(finalans==0):
	print("YES")
else:
	mark=[0]*len(arr2)
	countx=0
	finalans=0
	currval=tempval
	while(countx<len(arr2)):
		flag=-1
		for i in range(len(arr2)):
			if(mark[i]==0 and currval>=arr2[i][0]):
				tempflag=0
				for j in range(len(arr2)):
					if(j!=i and mark[j]==0):
						if(currval+arr2[i][1]<arr2[j][0]):
							tempflag=1
							break
				#print(tempflag)
				if(tempflag==0):
					flag=i
					
		if(flag==-1):
			print("NO")
			return
			break
		else:
			currval+=arr2[flag][1]
			mark[flag]=1
			countx+=1
	if(currval<0):
		print("NO")
	else:
		print("YES")



import math
import sys
from collections import defaultdict
#input = sys.stdin.readline
nt = lambda: list(map(int, input().split()))


def main():
    n, r = nt()
    projects = [tuple(nt()) for _ in range(n)]
    positive = [t for t in projects if t[1] > 0]
    negative = [t for t in projects if t[1] <= 0]

    ok = True
    for p in sorted(positive):
        if p[0] <= r:
            r += p[1]
        else:
            ok = False
            break
    if ok:
        for p in sorted(negative, key=lambda x: -x[0]-x[1]):
            if p[0] <= r:
                r += p[1]
                if r < 0:
                    ok = False
                    break
            else:
                ok = False
                break

    print('YES' if ok else 'NO')


def __starting_point():
    main()

__starting_point()

import sys
input = sys.stdin.readline
n,r=list(map(int,input().split()))
ABP,ABN=[],[]
for i in range(n):
  a,b=list(map(int,input().split()))
  if b>=0:
    ABP.append([a,b])
  else:
    ABN.append([a,b])
ABP.sort(key=lambda x:(x[0],x[1]))
chk=True
for i in range(len(ABP)):
  if ABP[i][0]>r:
    chk=False
  else:
    r+=ABP[i][1]
if chk==False:
  print("NO")
else:
  ABN.sort(key=lambda x:(x[0]+x[1],x[0]),reverse=True)
  for i in range(len(ABN)):
    a,b=ABN[i]
    if r<a:
      chk=False
    else:
      r+=b
  if chk==False or r<0:
    print("NO")
  else:
    print("YES")


import sys
input = sys.stdin.readline
n,r=list(map(int,input().split()))
ABP,ABN=[],[]
for i in range(n):
  a,b=list(map(int,input().split()))
  if b>=0:
    ABP.append([a,b])
  else:
    ABN.append([a,b])
ABP.sort(key=lambda x:(x[0],x[1]))
chk=True
for i in range(len(ABP)):
  if ABP[i][0]>r:
    chk=False
  else:
    r+=ABP[i][1]
if chk==False:
  print("NO")
else:
  ABN.sort(key=lambda x:(x[0]+x[1]),reverse=True)
  for i in range(len(ABN)):
    a,b=ABN[i]
    if r<a:
      chk=False
    else:
      r+=b
  if chk==False or r<0:
    print("NO")
  else:
    print("YES")


n,r=list(map(int,input().split()))
a=[]
b=[]
for _ in range(n):
    c,d=list(map(int,input().split()))
    if d<0:
        b.append([c,d])
    else:
        a.append([c,d])
a.sort(key = lambda x: x[0])
b.sort(key = lambda x: x[0]+x[1],reverse=True)
z=1
for i in a:
    if i[0]>r:
        z=0
        break
    r+=i[1]
for i in b:
    if i[0]>r:
        z=0
        break
    r+=i[1]
if z==0 or r<0:
    print('NO')
else:
    print('YES')
#print(a,b)


n,r = list(map(int,input().split()))
pl = []
mi = []
for _ in range(n):
	a,b = list(map(int,input().split()))
	if b >= 0:
		pl.append((a,b))
	else:
		mi.append((a,b))
pl.sort()
mi.sort(key=lambda t:t[0]+t[1])
mi.reverse()
for i,j in pl:
	if(r < i):
		print('NO')
		return
	else:
		r += j
for i,j in mi:
	if(r<i):
		print('NO')
		return
	else:
		r += j
if r < 0:
	print('NO')
else:
	print('YES')


import sys
input = sys.stdin.readline

from math import gcd, sqrt

n, r = map(int, input().split())
l = []
for _ in range(n):
	l.append(list(map(int, input().split())))
p = 0
while (p < n):
	if l[p][0] <= r and l[p][1] >= 0:
		r += l[p][1]
		l = l[:p] + l[p + 1:]
		p = 0
		n -= 1
	else:
		p += 1
if l == []:
	print("YES")
	return
ans = True
q = len(l)
for i in range(q):
	l[i][0] = max(l[i][0], -l[i][1])
l = sorted(l, key = lambda x: x[0] + x[1])
l.reverse()
#print(l, r)
for i in range(len(l)):
	if l[i][0] > r:
		ans = False
		break
	else:
		r += l[i][1]
if ans and r >= 0:
	print("YES")
else:
	print("NO")

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

proj_list = []
for _ in range(n):
    a, b = list(map(int, input().split()))
    proj_list.append([b, a, True])

def check(proj_list):
    nonlocal r

    while len(proj_list) > 0:
        i = 0
        while True:
            if i == len(proj_list):
                for prj in proj_list:
                    if prj[2]:
                        return False
                return True

            proj = proj_list[i]
            if r >= proj[1] and proj[2]:
                proj[2] = False
                r += proj[0]
                if r < 0:
                    return False
                break
            i += 1


#proj_list.sort(reverse=True)
raise_mmr = [x for x in proj_list if x[0] >= 0]
hard_work = [x for x in proj_list if x[0] < 0]
proj_list = sorted(raise_mmr, key=lambda x: x[0], reverse=True) + sorted(hard_work, key=lambda x: x[1] + x[0], reverse=True)

print("YES" if check(proj_list) else "NO")


n,r = map(int,input().split())

pt = []
nt = []
r2 = r 
for _ in range(n):
    a,b = map(int,input().split())
    r2 += b 
    if b >= 0:
        pt.append((a,b))
    else:
        nt.append((a,b))

if r2<0:
    print('NO');return

pt.sort()
nt.sort(key=lambda t:t[0]+t[1])

for a,b in pt:
    if r<a:
        print('NO');return
    r += b 

for a,b in nt:
    if r2 < a+b:
        print('NO');return
    r2 -= b 

print("YES")


a,b = map(int,input().split())
A = []
B = []
for i in range(a):
    q,w = map(int,input().split())
    if w<0:
        q = max(q,-w)
        B.append([q+w,q,w])
    else:
        A.append([q,w])
A.sort()
B.sort()
B.reverse()
q = True
i = 0
w = len(A)
while q == True and i<w:
    if b>=A[i][0]:
        b+=A[i][1]
        i+=1
    else:
        q = False
i = 0
w = len(B)
while q == True and i<w:
    if b>=B[i][1]:
        b+=B[i][2]
        i+=1
    else:
        q = False
if q == True and b>=0:
    print('YES')
else:
    print('NO')