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.

Polycarp can choose the order in which he completes projects. Furthermore, he can even skip some projects altogether.

To gain more experience (and money, of course) Polycarp wants to choose the subset of projects having maximum possible size and the order in which he will complete them, so he has enough rating before starting each project, and has non-negative rating after completing each project.

Your task is to calculate the maximum possible size of such subset of projects.


-----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 one integer — the size of the maximum possible subset (possibly, empty) of projects Polycarp can choose.


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

Output
3

Input
5 20
45 -6
34 -15
10 34
1 27
40 -45

Output
5

Input
3 2
300 -300
1 299
1 123

Output
3

Difficulty: introductory

Starter code:

Solutions:
'''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 status and r>=0 and sum(check)==len(check):
# 	print("YES")
# else:
# 	print("NO")

#print(eventsneg,eventspos)

print(max(check) + ans	)


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 status and r>=0 and sum(check)==len(check):
# 	print("YES")
# else:
# 	print("NO")
 
#print(eventsneg,eventspos)
 
print(max(check) + ans)

N, R = [int(x) for x in input().split()]
projects = [[int(x) for x in input().split()] for _ in range(N)]
pos = []
neg = []
for a, b in projects:
    if b < 0:
        neg.append((a, b))
    else:
        pos.append((a, b))
pos.sort()
ans = 0
for a, b in pos:
    if R >= a:
        R += b
        ans += 1
neg.sort(key=sum, reverse=True)
memo = {}
def dp(i, r):
    if(i, r) in memo:
        return memo[i, r]
    if i == len(neg):return 0
    a, b = neg[i]
    ans  = dp(i+1, r)
    if r >= a and r + b >= 0:
        ans = max(ans, dp(i+1, r + b) + 1)
    memo[i, r] = ans
    return ans
print( dp(0, R) + ans  )  


from bisect import bisect_right

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())
ppi = [(aa[i], bb[i]) for i in range(n) if bb[i] >= 0]
ppd = [(max(aa[i], -bb[i]), bb[i]) for i in range(n) if bb[i] < 0]
ppi.sort()
count = 0
for (a,b) in ppi:
    if a > r:
        break
    r += b
    count+=1
ppd.sort(reverse=True,key=lambda p: p[0] + p[1] )
dp = [[0]*(r+1) for _ in range(len(ppd)+1)]
dp[0][r] = count
for i,(a,b) in enumerate(ppd):
    for v in range(r+1):
        if v >= a and v+b >= 0:
            dp[i+1][v + b] = max(dp[i+1][v + b], dp[i][v] + 1)
        dp[i+1][v] = max(dp[i+1][v], dp[i][v])
print(max(dp[len(ppd)]))

import sys
input = sys.stdin.readline

n, r = map(int, input().split())
l = []
for _ in range(n):
	l.append(list(map(int, input().split())))
p = 0
ans = 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
		ans += 1
	else:
		p += 1
if l == []:
	print(ans)
	return
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)
dp = [[0 for _ in range(r + 1)] for _ in range(q + 1)]
for i in range(q):
	for j in range(r + 1):
		#dp[i][j] = dp[i][j-1]
		if j >= l[i][0] and 0 <= j + l[i][1] <= r:
			dp[i+1][j+l[i][1]] = max(dp[i+1][j+l[i][1]], dp[i][j] + 1)
		dp[i+1][j] = max(dp[i+1][j], dp[i][j])
# for i,x in enumerate(dp):
# 	print(i, *x)
print(max(dp[-1]) + ans)

from sys import stdin
from sys import setrecursionlimit as SRL; SRL(10**7)
rd = stdin.readline
rrd = lambda: list(map(int, rd().strip().split()))

n,r = rrd()


pos = []
neg = []

for i in range(n):
    a,b = rrd()
    if b < 0:
        neg.append([a,b])
    else:
        pos.append([a,b])

pos.sort(key=lambda x: x[0])
neg.sort(key=lambda x: x[0]+x[1])

ans = 0

for a,b in pos:

    if r>=a:
        r += b
        ans += 1
    else:
        break

dp = [[0]*105 for _i in range(60005)]

for i in range(r+10):
    for j in range(len(neg)):
        if i >= neg[j][0] and i+neg[j][1] >= 0:
            if j:
                dp[i][j] = max(dp[i][j], dp[i + neg[j][1]][j - 1] + 1,dp[i][j-1])
            else:
                dp[i][j] = 1
        else:
            if j:
                dp[i][j] = dp[i][j-1]


print(dp[r][len(neg)-1] + ans)


# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
from sys import stdin, stdout
import math
import copy
 
#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

dp = {}
 
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

valid = 0
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:
        break
    else:
        visited[idx] = 1
        r += b[idx]
        valid = i+1
        #print(idx,r)
        
dp[r] = valid
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)

#print(dp)
for i in range(len(tmp)):
    dp_tmp = copy.deepcopy(dp)
    
    for threshold in dp:
        if threshold>=tmp[i][0]:
            new_r = threshold + tmp[i][1]
            if new_r in dp_tmp:
                dp_tmp[new_r] = max(dp[new_r],dp[threshold]+1)
            else:
                dp_tmp[new_r] = dp[threshold]+1
    
    #print(dp_tmp)
    dp = dp_tmp
    
res = 0
#print(dp)
for key in dp:
    if key>=0:
        res = max(res,dp[key])
    
print(res)
    
        
 


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

pt = []
nt = []
r2 = r
result = 0

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

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

for a, b in pt:
    if r < a:
        break
    result += 1
    r += b

k = len(nt)
ws = [[0]*(k+1) for i in range(r+1)]

for i in range(1, k+1):
    for w in range(1, r+1):
        a, b = nt[i-1]
        if w+b >= 0 and a <= r and ws[r-a][i-1] >= ws[w][i-1]:
            ws[w][i] = max(ws[w][i-1], 1+ws[w+b][i-1])
        else:
            ws[w][i] = ws[w][i-1]


result += ws[r][k]
'''
print(*enumerate(nt))
print(r, k)
print(*enumerate(ws), sep='\n')
'''
print(result)

n,r=list(map(int,input().split()))
a=[list(map(int,input().split())) for i in range(n)]
pos = []
neg = []
ans=0
for x in a:
	if x[1]>0:
		pos.append(x)
	else:
		neg.append(x)
pos.sort(key=lambda k: k[0])
flag=True
for x in pos:
	if r>=x[0]:
		r+=x[1]
		ans+=1

neg.sort(key=lambda i: i[0]+i[1],reverse=True)
arr=[0]*(r+1)
for i in range(len(neg)):
	for j in range(neg[i][0],r+1):
		if j+neg[i][1]>=0:
			arr[j+neg[i][1]]=max(arr[j+neg[i][1]],arr[j]+1)
ans+=max(arr)
print(ans)


from collections import namedtuple

n, r = list(map(int, input().split()))
plus = []
minus = []
Project = namedtuple('Project', 'value a b')
for _ in range(n):
    a, b = list(map(int, input().split()))
    if b >= 0:
        plus.append((a, b))
    else:
        minus.append(Project(max(0, a + b), a, b))
plus.sort()
minus.sort(reverse=True)
ans = 0
for a, b in plus:
    if r >= a:
        r += b
        ans += 1
dp = [[-1 for _ in range(60001)] for _ in range(len(minus) + 1)]
dp[0][r] = 0
for i in range(len(dp) - 1):
    for j in range(len(dp[0])):
        if dp[i][j] == -1:
            continue
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        if j + minus[i].b >= 0 and minus[i].a <= j:
            dp[i + 1][j + minus[i].b] = max(dp[i + 1][j + minus[i].b], dp[i][j] + 1)
ans += max(dp[-1])
print(ans)


from functools import cmp_to_key
from operator import itemgetter


def main():
    n, r = list(map(int, input().split()))
    ps = [tuple(map(int, input().split())) for _ in range(n)]

    pos_ps = [(a, b) for a, b in ps if b >= 0]
    neg_ps = [(a, b) for a, b in ps if b < 0]

    def cmp(a, b):
        (aa, ab), (ba, bb) = a, b
        return max(aa, max(*b) - ab) - max(ba, max(*a) - bb)

    pos_ps.sort(key=itemgetter(0))
    neg_ps.sort(key=cmp_to_key(cmp))
    del cmp

    res = 0
    for a, b in pos_ps:
        if r >= a:
            res += 1
            r += b

    cur = [r]
    for a, b in neg_ps:
        nxt = [-1]*(len(cur)+1)
        for i, r in enumerate(cur):
            if r >= 0:
                nxt[i] = max(nxt[i], r)
                if r >= a:
                    nxt[i+1] = r + b
        while nxt[-1] < 0:
            nxt.pop()
        cur = nxt

    print(res + len(cur) - 1)


def __starting_point():
    main()

__starting_point()

from functools import cmp_to_key
from operator import itemgetter


def main():
    n, r = list(map(int, input().split()))
    ps = [tuple(map(int, input().split())) for _ in range(n)]

    pos_ps = [(a, b) for a, b in ps if b >= 0]
    neg_ps = [(a, b) for a, b in ps if b < 0]

    def cmp(a, b):
        (aa, ab), (ba, bb) = a, b
        return max(aa, max(*b) - ab) - max(ba, max(*a) - bb)

    pos_ps.sort(key=itemgetter(0))
    neg_ps.sort(key=cmp_to_key(cmp))
    del cmp

    res = 0
    for a, b in pos_ps:
        if r >= a:
            res += 1
            r += b

    cur = [r]
    for a, b in neg_ps:
        nxt = [-1]*(len(cur)+1)
        for i, r in enumerate(cur):
            if r >= 0:
                nxt[i] = max(nxt[i], r)
                if r >= a:
                    nxt[i+1] = r + b
        while nxt[-1] < 0:
            nxt.pop()
        cur = nxt

    print(res + len(cur) - 1)


def __starting_point():
    main()

__starting_point()

from functools import reduce

def doProject(r, proj, nproj):
    count=0
    for i in range(len(proj)):
        if(proj[i][0]<=r):
            r+=proj[i][1]
            count+=1
        else:
            pass

    dp=[[0 for j in range(r+1)] for i in range(len(nproj)+1)]
    dp[0][r] = count

    for i in range(len(nproj)):
        for cr in range(r+1):
            if(nproj[i][0] <= cr and cr + nproj[i][1] >= 0):
                dp[i+1][cr + nproj[i][1]] = max(dp[i+1][cr + nproj[i][1]], dp[i][cr]+1)

            dp[i+1][cr] = max(dp[i+1][cr], dp[i][cr])

    count = reduce(lambda x,y: max(x,y) , dp[len(nproj)])
    
    return count

def main():

    n, r = map(int, input().rstrip().split())
    
    proj, nproj = [], []
    for _ in range(n):

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

        if(temp[1]<0):
            nproj.append(temp)
        else:
            proj.append(temp)

    proj.sort()
    nproj.sort(reverse=True, key=lambda x: x[0]+x[1])
    
    ans = doProject(r,proj, nproj)
    print(ans)


def __starting_point():
    main()
__starting_point()

import math
import sys
from collections import defaultdict

# input = sys.stdin.readline
nt = lambda: 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]

    max_pos = 0
    for p in sorted(positive):
        if p[0] <= r:
            r += p[1]
            max_pos += 1
        else:
            break
    negative.sort(key=lambda x: -x[0] - x[1])
    MAX = 60001
    dp = [[-1 for _ in range(MAX)] for _ in range(len(negative)+1)]
    dp[0][r] = 0
    for i in range(len(negative)):
        for j in range(MAX):
            if dp[i][j] == -1:
                continue
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
            if j >= negative[i][0] and j+negative[i][1] >= 0:
                dp[i+1][j+negative[i][1]] = max(dp[i+1][j+negative[i][1]], dp[i][j]+1)
    max_neg = 0
    for i in range(MAX):
        max_neg = max(max_neg, dp[len(negative)][i])

    print(max_pos + max_neg)


def __starting_point():
    main()
__starting_point()

from math import *

MOD = int(1e9)+7

def nextInt():
    return int(input())

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

def YN(x):
    return "YES" if x else "NO"

def solve():
    n,r = nextInts()
    pos = []
    neg = []
    for i in range(n):
        a,b = nextInts()
        a = max(a,-b)
        if b >= 0:
            pos.append((a,b))
        else:
            neg.append((a,b))
    pos.sort(key = lambda x:x[0])
    neg.sort(key = lambda x:-(x[0]+x[1]))
    ans = 0
    for t in pos:
        if r >= t[0]:
            r += t[1]
            ans += 1

    dp = [-MOD]*60001
    dp[r] = ans

    for t in neg:
        for j in range(t[0],60001):
            dp[j+t[1]] = max(dp[j+t[1]],dp[j]+1)
    return max(dp)

print(solve())

# q = nextInt()
# for i in range(q):
#     print(YN(solve()))


# -*- coding: utf-8 -*-
"""
Created on Thu Jan  9 11:12:02 2020

@author: Rodro
"""

inp = str(input()).split()
size = int(inp[0])
r = int(inp[1])

pos = []
neg = []
for i in range(size):
    inp = str(input()).split()
    a = int(inp[0])
    b = int(inp[1])
    if b >= 0: pos.append((a, b))
    else: neg.append((a,b))
pos = sorted(pos)
projects = 0
for ab in pos:
    a, b = ab
    if r >= a:
        r += b
        projects += 1
    else: break

neg = sorted(neg, key = lambda ab: ab[0] + ab[1], reverse = True)
n = len(neg)
dp = [[0]*(r + 1) for _ in range(n + 1)]
dp[0][r] = projects
for i in range(0, n):
    for j in range(0, r + 1):
        if j >= neg[i][0] and j + neg[i][1] >= 0:
            dp[i + 1][j + neg[i][1]] = max(dp[i + 1][j + neg[i][1]], dp[i][j] + 1)
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])

print(max(dp[n]))

#https://codeforces.com/contest/1203/problem/F2 

n, r = list(map(int, input().split()))
arr  = [list(map(int, input().split())) for _ in range(n)] 

def solve1(cur, arr):
    cnt=0

    while len(arr) > 0:
        max_inc = -9999
        choose  = None 
        for a, b in arr:
            if cur >= a and max_inc < b:
                max_inc = b
                choose  = a
                
        if choose is None:
            flg=False
            break
        
        cnt+=1
        cur+=max_inc
        arr.remove([choose, max_inc])

    return cur, cnt

arr1 = [[x, y] for x, y in arr if y >= 0]
arr2 = [[x, y] for x, y in arr if y <  0]

r, cnt = solve1(r, arr1) 
n      = len(arr2) 
arr2   = [[]] + sorted(arr2, key=lambda x:x[0]+x[1], reverse=True) 
dp     = [[-1] * (n+1) for _ in range(n+1)]

for i in range(n+1):
    dp[i][0] = r
    
for i in range(1, n+1):
    for j in range(1, i+1):
        dp[i][j] = dp[i-1][j]
        if dp[i-1][j-1] >= arr2[i][0] and dp[i-1][j-1] + arr2[i][1] >= 0:
            dp[i][j] = max(dp[i][j], dp[i-1][j-1]+arr2[i][1])
            
ans = 0            
for j in range(n+1):
    if dp[n][j] >= 0:
        ans = j

print(ans+cnt)        

#3 4
#4 6
#10 -2
#8 -1


n, r = list(map(int, input().split()))
a = []
cnt = 0
for i in range(n):
    a.append([int(j) for j in input().split()])
flag = True
while flag:
    flag = False
    for i in a:
        if r >= i[0] and i[1] >= 0:
            flag = True
            r += i[1]
            cnt += 1
            a.remove(i)
            break
a = sorted(a, key=lambda x: x[0] + x[1])
dp = [[0] * (r + 1) for i in range(len(a) + 1)]
for i in range(len(a)):
	for j in range(r + 1):
		dp[i][j] = dp[i - 1][j]
		if j >= a[i][0] and j + a[i][1] >= 0:
			dp[i][j] = max(dp[i][j], dp[i - 1][j + a[i][1]] + 1)
print(cnt + dp[len(a) - 1][r])
#print(dp, a)


n, r = list(map(int, input().split()))
a = []
cnt = 0
for i in range(n):
    a.append([int(j) for j in input().split()])
flag = True
while flag:
    flag = False
    for i in a:
        if r >= i[0] and i[1] >= 0:
            flag = True
            r += i[1]
            cnt += 1
            a.remove(i)
            break
a = sorted(a, key=lambda x: x[0] + x[1])
dp = [[0] * (r + 1) for i in range(len(a) + 1)]
for i in range(len(a)):
	for j in range(r + 1):
		dp[i][j] = dp[i - 1][j]
		if j >= a[i][0] and j + a[i][1] >= 0:
			dp[i][j] = max(dp[i][j], dp[i - 1][j + a[i][1]] + 1)
print(cnt + dp[len(a) - 1][r])
#print(dp, a)


z, r = list(map(int, input().split()))
a = []
cnt = 0
for i in range(z):
    a.append([int(j) for j in input().split()])
flag = True
while flag:
    flag = False
    for i in a:
        if r >= i[0] and i[1] >= 0:
            flag = True
            r += i[1]
            cnt += 1
            a.remove(i)
            break
a = sorted(a, key=lambda x: x[0] + x[1])
dp = [[0] * (r + 1) for i in range(len(a) + 1)]
for i in range(len(a)):
	for j in range(r + 1):
		dp[i][j] = dp[i - 1][j]
		if j >= a[i][0] and j + a[i][1] >= 0:
			dp[i][j] = max(dp[i][j], dp[i - 1][j + a[i][1]] + 1)
print(cnt + dp[len(a) - 1][r])
#print(dp, a)


N, R = [int(x) for x in input().split()]
projects = [[int(x) for x in input().split()] for _ in range(N)]
pos = []
neg = []
for a, b in projects:
    if b < 0:
        neg.append((a, b))
    else:
        pos.append((a, b))
pos.sort()
ans = 0
for a, b in pos:
    if R >= a:
        R += b
        ans += 1
neg.sort(key=sum, reverse=True)
memo = {}
def dp(i, r):
    if(i, r) in memo:
        return memo[i, r]
    if i == len(neg):return 0
    a, b = neg[i]
    ans  = dp(i+1, r)
    if r >= a and r + b >= 0:
        ans = max(ans, dp(i+1, r + b) + 1)
    memo[i, r] = ans
    return ans
print( dp(0, R) + ans  ) 
#JSR


N, R = [int(x) for x in input().split()]
projects = [[int(x) for x in input().split()] for _ in range(N)]
pos = []
neg = []
for a, b in projects:
    if b < 0:
        neg.append((a, b))
    else:
        pos.append((a, b))
pos.sort()
ans = 0
for a, b in pos:
    if R >= a:
        R += b
        ans += 1
neg.sort(key=sum, reverse=True)
memo = {}
def dp(i, r):
    if(i, r) in memo:
        return memo[i, r]
    if i == len(neg):return 0
    a, b = neg[i]
    ans  = dp(i+1, r)
    if r >= a and r + b >= 0:
        ans = max(ans, dp(i+1, r + b) + 1)
    memo[i, r] = ans
    return ans
print( dp(0, R) + ans  ) 
#purvikaurraina



N, R = [int(x) for x in input().split()]
projects = [[int(x) for x in input().split()] for _ in range(N)]
pos = []
neg = []
for a, b in projects:
    if b < 0:
        neg.append((a, b))
    else:
        pos.append((a, b))
pos.sort()
ans = 0
for a, b in pos:
    if R >= a:
        R += b
        ans += 1
neg.sort(key=sum, reverse=True)
memo = {}
def dp(i, r):
    if(i, r) in memo:
        return memo[i, r]
    if i == len(neg):return 0
    a, b = neg[i]
    ans  = dp(i+1, r)
    if r >= a and r + b >= 0:
        ans = max(ans, dp(i+1, r + b) + 1)
    memo[i, r] = ans
    return ans
print( dp(0, R) + ans  )


def myFunc(e):
    return e[0] + e[1]

count, rating = list(map(int, input().split()))
goodJob = []
badJob = []

taken = 0

for i in range(count):
    a, b = list(map(int, input().split()))
    if b >= 0:
        goodJob.append([a, b])
    else:
        badJob.append([a, b])

goodJob.sort()
badJob.sort(reverse=True, key=myFunc)

for job in goodJob:
    if job[0] <= rating:
        rating += job[1]
        taken += 1
    else:
        break

dp = []

for i in range(len(badJob) + 1):
    row = []
    for j in range(rating + 2):
        row.append(0)
    dp.append(row)

dp[0][rating] = taken

for i in range(len(badJob)):
    for curRating in range(rating + 1):
        if curRating >= badJob[i][0] and curRating + badJob[i][1] >= 0: 
            dp[i + 1][curRating + badJob[i][1]] = max(dp[i + 1][curRating + badJob[i][1]], dp[i][curRating] + 1)
        dp[i + 1][curRating] = max(dp[i + 1][curRating], dp[i][curRating])

ans = 0

for curRating in range(rating + 1): 
    ans = max(ans, dp[len(badJob)][curRating])

print(ans)





from operator import itemgetter, attrgetter
n,r=list(map(int,input().split()))
ps,neg=[],[]
for i in range(n):
    a,b=list(map(int,input().split()))
    if(b>=0):
        ps.append([a,b,-a-b])
    else:
        neg.append([a,b,-a-b])
ps=sorted(ps)
neg=sorted(neg,key=itemgetter(2))
ps=ps+neg
#print(*ps)
dp=[-float('inf')]*(n+1)
dp[0]=r
for i in range(n):
    for j in range(n-1,-1,-1):
        if(dp[j]>=ps[i][0]):
            dp[j+1]=max(dp[j+1],dp[j]+ps[i][1])
for j in range(n,-1,-1):
    if(dp[j]>=0):
        print(j)
        break