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

Source: codeforces | Difficulty: HARD
Tags: Dynamic programming

Greedy algorithms


Solutions:
from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import ceil, floor
from copy import *
from collections import deque, defaultdict
from collections import Counter as counter
from itertools import combinations
from itertools import permutations as permutate
from bisect import bisect_left as bl
from operator import *
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192
from sys import stderr

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

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 1000000007

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())

def nextline():
	out('\n')

def testcase(t):
	for p in range(t):
		solve()

def pow(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
from functools import reduce

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

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

def prefix_sum(ar):
	return list(accumulate(ar))

def suffix_sum(ar):
	return list(accumulate(ar[::-1]))[::-1]

def N():
	return int(inp())
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
from collections import defaultdict

def numberOfSetBits(i):
	i = i - (i >> 1 & 1431655765)
	i = (i & 858993459) + (i >> 2 & 858993459)
	return ((i + (i >> 4) & 252645135) * 16843009 & 4294967295) >> 24
from decimal import *

def solve():

	class SegmentTree:

		def __init__(self, data, default=0, func=max):
			self._default = default
			self._func = func
			self._len = len(data)
			self._size = _size = 1 << (self._len - 1).bit_length()
			self.data = [default] * _size + data + [default] * (_size - self._len)
			for i in range(_size - 1, -1, -1):
				self.data[i] = func(self.data[2 * i], self.data[2 * 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):
			start += self._size
			stop += self._size
			res_left = res_right = self._default
			while start < stop:
				if start & 1:
					res_left = self._func(res_left, self.data[start])
					start += 1
				if stop & 1:
					stop -= 1
					res_right = self._func(self.data[stop], res_right)
				start >>= 1
				stop >>= 1
			return self._func(res_left, res_right)

		def __repr__(self):
			return 'SegmentTree({0})'.format(self.data)
	(n, r) = sep()
	posrat = []
	negrat = []
	c = 0
	for _ in range(n):
		(a, b) = sep()
		if b >= 0:
			posrat.append((a, b))
		else:
			negrat.append((a, b))
	posrat.sort()

	def f(x):
		return x[0] + x[1]
	negrat.sort(reverse=True, key=f)
	cr = r
	for i in posrat:
		(ai, bi) = i
		if ai <= cr:
			c += 1
			cr += bi
	l = len(negrat)
	R = cr
	dp = [[0] * (R + 1) for _ in range(l + 1)]
	for i in range(1, l + 1):
		for j in range(R, -1, -1):
			dp[i][j] = dp[i - 1][j]
			if j - negrat[i - 1][1] >= negrat[i - 1][0] and j - negrat[i - 1][1] <= R:
				dp[i][j] = max(dp[i][j], dp[i - 1][j - negrat[i - 1][1]] + 1)
	m = 0
	for i in range(1, l + 1):
		for j in range(R, -1, -1):
			m = max(m, dp[i][j])
	print(m + c)
solve()


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


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


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


(n, r) = 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])


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
		elif j:
			dp[i][j] = dp[i][j - 1]
print(dp[r][len(neg) - 1] + 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)


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


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)]
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)
print(max(check) + ans)


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


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()
dp = [[0 for _ in range(r + 1)] for _ in range(q + 1)]
for i in range(q):
	for j in range(r + 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])
print(max(dp[-1]) + ans)


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)
main()


import math
import sys
from collections import defaultdict
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)
main()


(n, r) = 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)


from math import *
MOD = int(1000000000.0) + 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())


from sys import stdin, stdout
import math
import copy
(N, r) = [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):
		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
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)
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
	dp = dp_tmp
res = 0
for key in dp:
	if key >= 0:
		res = max(res, dp[key])
print(res)


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


(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(result)