The hero of the Cut the Rope game is a little monster named Om Nom. He loves candies. And what a coincidence! He also is the hero of today's problem. [Image] 

One day, Om Nom visited his friend Evan. Evan has n candies of two types (fruit drops and caramel drops), the i-th candy hangs at the height of h_{i} centimeters above the floor of the house, its mass is m_{i}. Om Nom wants to eat as many candies as possible. At the beginning Om Nom can make at most x centimeter high jumps. When Om Nom eats a candy of mass y, he gets stronger and the height of his jump increases by y centimeters.

What maximum number of candies can Om Nom eat if he never eats two candies of the same type in a row (Om Nom finds it too boring)?


-----Input-----

The first line contains two integers, n and x (1 ≤ n, x ≤ 2000) — the number of sweets Evan has and the initial height of Om Nom's jump. 

Each of the following n lines contains three integers t_{i}, h_{i}, m_{i} (0 ≤ t_{i} ≤ 1; 1 ≤ h_{i}, m_{i} ≤ 2000) — the type, height and the mass of the i-th candy. If number t_{i} equals 0, then the current candy is a caramel drop, otherwise it is a fruit drop.


-----Output-----

Print a single integer — the maximum number of candies Om Nom can eat.


-----Examples-----
Input
5 3
0 2 4
1 3 1
0 8 3
0 20 10
1 5 5

Output
4



-----Note-----

One of the possible ways to eat 4 candies is to eat them in the order: 1, 5, 3, 2. Let's assume the following scenario:  Initially, the height of Om Nom's jump equals 3. He can reach candies 1 and 2. Let's assume that he eats candy 1. As the mass of this candy equals 4, the height of his jump will rise to 3 + 4 = 7.  Now Om Nom can reach candies 2 and 5. Let's assume that he eats candy 5. Then the height of his jump will be 7 + 5 = 12.  At this moment, Om Nom can reach two candies, 2 and 3. He won't eat candy 2 as its type matches the type of the previously eaten candy. Om Nom eats candy 3, the height of his jump is 12 + 3 = 15.  Om Nom eats candy 2, the height of his jump is 15 + 1 = 16. He cannot reach candy 4.

Difficulty: MEDIUM
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
(n, x) = (int(x) for x in input().split())
cs = []
for i in range(n):
	cs.append([int(x) for x in input().split()])
	if cs[-1][0] > 0:
		cs[-1][0] = 1

def try_eat(t0):
	h0 = x
	used = set()
	while True:
		m0 = 0
		i0 = -1
		for (i, (t, h, m)) in enumerate(cs):
			if t != t0 and h <= h0 and (m > m0) and (i not in used):
				m0 = m
				i0 = i
		if i0 == -1:
			break
		used.add(i0)
		h0 += cs[i0][2]
		t0 = 1 - t0
	return len(used)
print(max(try_eat(0), try_eat(1)))


from bisect import bisect_left
(n, x) = map(int, input().split())
(s, a, b) = (0, [[], []], [[], []])
for i in range(n):
	(t, h, m) = map(int, input().split())
	a[t].append((h, m))
for t in [0, 1]:
	a[t].sort(key=lambda x: x[0])
	for (h, m) in a[t]:
		if h > x:
			break
		b[t].append(m)
	b[t].sort()
for t in [0, 1]:
	(y, i, c) = (x, [len(b[0]), len(b[1])], [b[0][:], b[1][:]])
	while c[t]:
		y += c[t].pop()
		t = 1 - t
		while i[t] < len(a[t]):
			(h, m) = a[t][i[t]]
			if h > y:
				break
			c[t].insert(bisect_left(c[t], m), m)
			i[t] += 1
	s = max(s, i[0] + i[1] - len(c[0]) - len(c[1]))
print(s)


a = input().split(' ')
h = int(a[1])
n = int(a[0])
candies = []
for i in range(n):
	s = input().split(' ')
	candies.append([int(s[0]), int(s[1]), int(s[2])])
zap = []
for i in range(n):
	zap.append(candies[i])

def eat(bl, cand, h):
	ch = h
	color = bl
	for i in range(n):
		maxJ = -1
		maxM = -1
		for j in range(len(cand)):
			if cand[j][0] == color:
				if cand[j][2] >= maxM and ch >= cand[j][1]:
					maxJ = j
					maxM = cand[j][2]
		if maxM == -1:
			return i
		else:
			color = 1 - color
			ch += maxM
			cand.remove(cand[maxJ])
	return n
a = eat(1, candies, h)
b = eat(0, zap, h)
if a > b:
	print(a)
else:
	print(b)


def solve(p, n, x, t, h, m):
	(used, xx, ans) = ([0] * n, x, 0)
	while True:
		k = -1
		for i in range(n):
			if used[i] == 0 and t[i] == p and (h[i] <= xx) and (k == -1 or m[i] > m[k]):
				k = i
		if k == -1:
			break
		ans += 1
		xx += m[k]
		used[k] = 1
		p = p ^ 1
	return ans
(n, x) = map(int, input().split())
(t, h, m) = ([0] * n, [0] * n, [0] * n)
for i in range(n):
	(t[i], h[i], m[i]) = map(int, input().split())
print(max(solve(0, n, x, t, h, m), solve(1, n, x, t, h, m)))


(n, x) = list(map(int, input().split()))
a = []
b = []
for i in range(n):
	(t, h, m) = list(map(int, input().split()))
	if t:
		a.append((h, m))
	else:
		b.append((h, m))
counter1 = 0
now = True
a1 = a[:]
b1 = b[:]
x2 = x
while 1:
	if now:
		if len(a) == 0:
			break
		i = 0
		maxx = 0
		mi = 0
		for kor in a:
			if kor[0] <= x and maxx < kor[1]:
				maxx = kor[1]
				mi = i
			i += 1
		if maxx == 0:
			break
		x += maxx
		a.pop(mi)
		counter1 += 1
		now = False
	else:
		if len(b) == 0:
			break
		i = 0
		maxx = 0
		mi = 0
		for kor in b:
			if kor[0] <= x and maxx < kor[1]:
				maxx = kor[1]
				mi = i
			i += 1
		if maxx == 0:
			break
		x += maxx
		b.pop(mi)
		counter1 += 1
		now = True
counter2 = 0
now = False
while 1:
	if now:
		if len(a1) == 0:
			break
		i = 0
		maxx = 0
		mi = 0
		for kor in a1:
			if kor[0] <= x2 and maxx < kor[1]:
				maxx = kor[1]
				mi = i
			i += 1
		if maxx == 0:
			break
		x2 += maxx
		a1.pop(mi)
		counter2 += 1
		now = False
	else:
		if len(b1) == 0:
			break
		i = 0
		maxx = 0
		mi = 0
		for kor in b1:
			if kor[0] <= x2 and maxx < kor[1]:
				maxx = kor[1]
				mi = i
			i += 1
		if maxx == 0:
			break
		x2 += maxx
		b1.pop(mi)
		counter2 += 1
		now = True
print(counter1 if counter1 > counter2 else counter2)


(n, x) = [int(c) for c in input().split()]
candies = []
for i in range(n):
	candies.append([int(c) for c in input().split()])
candies.sort(key=lambda x: x[2], reverse=True)

def find_best(candies, x, step):
	for i in range(len(candies)):
		if candies[i][0] == step and candies[i][1] <= x:
			return i
	return -1
eated = [0, 0]
for startWith in range(2):
	step = startWith
	c1 = candies[:]
	tmp = find_best(c1, x, step)
	x1 = x
	while tmp != -1:
		eated[startWith] += 1
		x1 = x1 + c1[tmp][2]
		step = (step + 1) % 2
		c1.pop(tmp)
		tmp = find_best(c1, x1, step)
print(max(eated))


from operator import itemgetter

def has_to_eat(food_type, height, food):
	result = 0
	for candie in food:
		if candie[0] == food_type or food_type == -1:
			if height >= candie[1]:
				candie[1] = 1000000000000000000
				return (candie[0], candie[2])
	return result

class CodeforcesTask436ASolution:

	def __init__(self):
		self.result = ''
		self.n_x = []
		self.candies = []

	def read_input(self):
		self.n_x = [int(x) for x in input().split(' ')]
		for x in range(self.n_x[0]):
			self.candies.append([int(x) for x in input().split(' ')])

	def process_task(self):
		self.candies = sorted(self.candies, key=itemgetter(2), reverse=True)
		jump = self.n_x[1]
		eat = 1
		candies = [x.copy() for x in self.candies]
		next = has_to_eat(eat, jump, candies)
		eaten = 0
		while next:
			eaten += 1
			jump += next[1]
			if next[0]:
				eat = 0
			else:
				eat = 1
			next = has_to_eat(eat, jump, candies)
		jump = self.n_x[1]
		eat = 0
		candies = [x.copy() for x in self.candies]
		next = has_to_eat(eat, jump, candies)
		eaten1 = 0
		while next:
			eaten1 += 1
			jump += next[1]
			if next[0]:
				eat = 0
			else:
				eat = 1
			next = has_to_eat(eat, jump, candies)
		self.result = str(max(eaten, eaten1))

	def get_result(self):
		return self.result

def __starting_point():
	Solution = CodeforcesTask436ASolution()
	Solution.read_input()
	Solution.process_task()
	print(Solution.get_result())
__starting_point()


(n, x) = map(int, input().split())
count = 0
ans = 0
curr = 0
fruit = []
caramel = []
for i in range(n):
	(t, h, m) = map(int, input().split())
	if t == 0:
		caramel.append((h, m))
	else:
		fruit.append((h, m))
caramel = sorted(caramel)
fruit = sorted(fruit)
fruit2 = fruit[:]
caramel2 = caramel[:]
x2 = x

def add_to_mass(arr, x):
	candy = 0
	curr = 0
	for i in range(len(arr)):
		if arr[i][0] <= x:
			if arr[i][1] >= candy:
				candy = arr[i][1]
				curr = i
	if candy == 0:
		return 0
	arr.pop(curr)
	return candy
while True:
	curr = add_to_mass(fruit, x)
	if curr == 0:
		break
	else:
		x += curr
	count += 1
	curr = add_to_mass(caramel, x)
	if curr == 0:
		break
	else:
		x += curr
	count += 1
ans = count
count = 0
while True:
	curr = add_to_mass(caramel2, x2)
	if curr == 0:
		break
	else:
		x2 += curr
	count += 1
	curr = add_to_mass(fruit2, x2)
	if curr == 0:
		break
	else:
		x2 += curr
	count += 1
ans = max(count, ans)
print(ans)


import re
import inspect
from sys import argv, exit
from copy import copy

def rstr():
	return input()

def rint():
	return int(input())

def rints(splitchar=' '):
	return [int(i) for i in input().split(splitchar)]

def varnames(obj, namespace=globals()):
	return [name for name in namespace if namespace[name] is obj]

def pvar(var, override=False):
	prnt(varnames(var), var)

def prnt(*args, override=False):
	if '-v' in argv or override:
		print(*args)

class Candy:

	def __init__(self, stuff):
		self.type = bool(stuff[0])
		self.height = stuff[1]
		self.mass = stuff[2]

	def __str__(self):
		return '{} h{} m{}'.format(self.type, self.height, self.mass)

	def __repr__(self):
		return str(self)

def main(h, candies, last_type):
	eaten = []
	neaten = 0
	edible = sorted([c for c in candies if c.height <= h and c.type != last_type], key=lambda c: c.mass)
	prnt('h', h)
	prnt('last_type', last_type)
	prnt('edible', edible)
	while True:
		if edible:
			candy = edible.pop(-1)
			candies.remove(candy)
			prnt('eaten', candy)
			eaten.append(candy)
			neaten += 1
			last_type = not last_type
			h += candy.mass
		else:
			break
		edible = sorted([c for c in candies if c.height <= h and c.type != last_type], key=lambda c: c.mass)
		prnt(edible)
	return neaten

def __starting_point():
	(n, h) = rints()
	candies = [Candy(rints()) for i in range(n)]
	prnt(candies)
	one = main(h, copy(candies), False)
	two = main(h, copy(candies), True)
	pvar(one)
	pvar(two)
	print(max(one, two))
__starting_point()


import sys
f = sys.stdin
(n, x) = map(int, f.readline().strip().split())
kon = []
kon0 = []
kon1 = []
for i in range(n):
	(ti, hi, mi) = map(int, f.readline().strip().split())
	kon.append([ti, hi, mi])
	if ti == 0:
		kon0.append([hi, mi])
	else:
		kon1.append([hi, mi])

def ksort(item):
	if item[0] <= x:
		return -item[1]
	else:
		return item[0] - item[1] / 10000
kon0.sort(key=ksort)
kon1.sort(key=ksort)
t0 = kon0[:]
t1 = kon1[:]
tx = x
s = 0
i0 = 0
not_end = True
while not_end:
	if i0 % 2 == 0 and len(kon0) > 0 and (x >= kon0[0][0]):
		s += 1
		x += kon0[0][1]
		del kon0[0]
		kon0.sort(key=ksort)
		kon1.sort(key=ksort)
		i0 += 1
	elif i0 % 2 == 1 and len(kon1) > 0 and (x >= kon1[0][0]):
		s += 1
		x += kon1[0][1]
		del kon1[0]
		kon0.sort(key=ksort)
		kon1.sort(key=ksort)
		i0 += 1
	else:
		not_end = False
s1 = s
kon0 = t0
kon1 = t1
x = tx
s = 0
i0 = 1
not_end = True
while not_end:
	if i0 % 2 == 0 and len(kon0) > 0 and (x >= kon0[0][0]):
		s += 1
		x += kon0[0][1]
		del kon0[0]
		kon0.sort(key=ksort)
		i0 += 1
	elif i0 % 2 == 1 and len(kon1) > 0 and (x >= kon1[0][0]):
		s += 1
		x += kon1[0][1]
		del kon1[0]
		kon1.sort(key=ksort)
		i0 += 1
	else:
		not_end = False
print(max(s, s1))


(n, x) = map(int, input().split())
can = [[], []]
for i in range(n):
	(a, b, c) = map(int, input().split())
	can[a].append((b, c))
ans = 0
for nturn in range(2):
	u = [[], []]
	for i in range(2):
		for j in range(len(can[i])):
			u[i].append(False)
	nx = x
	nw = 0
	turn = nturn
	for i in range(n):
		mx = -1
		bj = -1
		for j in range(len(can[turn])):
			if not u[turn][j] and can[turn][j][0] <= nx and (can[turn][j][1] > mx):
				bj = j
				mx = can[turn][j][1]
		if bj != -1:
			nx += mx
			u[turn][bj] = True
			nw += 1
		else:
			break
		turn = (turn + 1) % 2
	ans = max(ans, nw)
print(ans)


(n, height) = map(int, input().split())
caramel = []
frut = []
h = height
for i in range(n):
	(x, y, z) = map(int, input().split())
	if x == 0:
		caramel.append([y, z])
	else:
		frut.append([y, z])
caramel.sort()
frut.sort()
q1 = caramel.copy()
q2 = frut.copy()
ans = f2 = 0
f1 = 1
a1 = 0
while a1 < len(caramel) and (f1 or f2):
	a1 += 1
	if f1:
		cm = f1 = flag1 = 0
		for i in range(len(caramel)):
			if caramel[i][0] != 0 and caramel[i][0] <= height:
				if caramel[i][1] > cm:
					cm = caramel[i][1]
					ic = i
					flag1 = 1
			elif caramel[i][0] > height:
				break
		if flag1:
			height += cm
			caramel[ic] = [0, 0]
			f2 = 1
			ans += 1
		else:
			break
	if f2:
		fm = f2 = flag2 = 0
		for i in range(len(frut)):
			if frut[i][0] != 0 and frut[i][0] <= height:
				if frut[i][1] > fm:
					fm = frut[i][1]
					iff = i
					flag2 = 1
			elif frut[i][0] > height:
				break
		if flag2:
			height += fm
			frut[iff] = [0, 0]
			f1 = 1
			ans += 1
		else:
			break
f2 = 1
f1 = anss = 0
a2 = 0
while a2 < len(q2) and (f1 or f2):
	a2 += 1
	if f2:
		fm = flag2 = f2 = 0
		for i in range(len(q2)):
			if q2[i][0] != 0 and q2[i][0] <= h:
				if q2[i][1] > fm:
					fm = q2[i][1]
					iff = i
					flag2 = 1
			elif q2[i][0] > h:
				break
		if flag2:
			h += fm
			q2[iff] = [0, 0]
			f1 = 1
			anss += 1
		else:
			break
	if f1:
		cm = flag1 = f1 = 0
		for i in range(len(q1)):
			if q1[i][0] <= h:
				if q1[i][1] > cm:
					cm = q1[i][1]
					ic = i
					flag1 = 1
			elif q1[i][0] > h:
				break
		if flag1:
			h += cm
			q1[ic] = [0, 0]
			f2 = 1
			anss += 1
		else:
			break
print(max(ans, anss))


import sys
from operator import itemgetter

def main():
	str = sys.stdin.readline()
	tokens = str.split()
	n = int(tokens[0])
	x = int(tokens[1])
	s1 = []
	s2 = []
	for i in range(n):
		str = sys.stdin.readline()
		tokens = str.split()
		t = int(tokens[0])
		h = int(tokens[1])
		m = int(tokens[2])
		if t == 0:
			s1.append((h, m))
		else:
			s2.append((h, m))
	s1 = sorted(s1, key=itemgetter(0))
	s1 = sorted(s1, key=itemgetter(1), reverse=True)
	s2 = sorted(s2, key=itemgetter(0))
	s2 = sorted(s2, key=itemgetter(1), reverse=True)
	s1A = s1[:]
	s2A = s2[:]
	jumpA = x
	candiesA = 0
	currentA = s1A
	while True:
		found = 0
		for i in range(len(currentA)):
			if currentA[i][0] <= jumpA:
				found = 1
				candiesA = candiesA + 1
				jumpA = jumpA + currentA[i][1]
				del currentA[i]
				break
		if found == 1:
			if currentA == s1A:
				currentA = s2A
			else:
				currentA = s1A
		else:
			break
	s1B = s1[:]
	s2B = s2[:]
	jumpB = x
	candiesB = 0
	currentB = s2B
	while True:
		found = 0
		for i in range(len(currentB)):
			if currentB[i][0] <= jumpB:
				found = 1
				candiesB = candiesB + 1
				jumpB = jumpB + currentB[i][1]
				del currentB[i]
				break
		if found == 1:
			if currentB == s1B:
				currentB = s2B
			else:
				currentB = s1B
		else:
			break
	print(max(candiesA, candiesB))

def __starting_point():
	main()
__starting_point()


import queue
(n, maxh) = [int(x) for x in input().split()]
car = []
fru = []
hcar = queue.PriorityQueue(2000)
hfru = queue.PriorityQueue(2000)
for i in range(n):
	(a, b, c) = [int(x) for x in input().split()]
	if a == 0:
		car.append((b, c))
	else:
		fru.append((b, c))
pcar = 0
mcar = len(car)
pfru = 0
mfru = len(fru)
car.sort()
fru.sort()
eaten = 0

def getinh():
	nonlocal pcar
	nonlocal pfru
	while pcar < mcar and car[pcar][0] <= maxh:
		hcar.put(-car[pcar][1])
		pcar += 1
	while pfru < mfru and fru[pfru][0] <= maxh:
		hfru.put(-fru[pfru][1])
		pfru += 1
getinh()
while not hcar.empty() and (not hfru.empty()):
	eaten += 2
	maxh -= hcar.get() + hfru.get()
	getinh()
if hcar.empty():
	now = 0
else:
	now = 1
while True:
	if now == 0:
		if hfru.empty():
			break
		else:
			now = 1
			maxh -= hfru.get()
	elif hcar.empty():
		break
	else:
		now = 0
		maxh -= hcar.get()
	eaten += 1
	getinh()
print(eaten)


import copy
(n, xx) = map(int, input().split())
firstorig = list()
secondorig = list()
for i in range(n):
	(t, h, m) = map(int, input().split())
	if t == 0:
		firstorig.append((h, m))
	else:
		secondorig.append((h, m))
firstres = 0
first = copy.deepcopy(firstorig)
second = copy.deepcopy(secondorig)
curmaxjump = xx
while True:
	if len(first) > 0:
		i = 0
		weight = 0
		for x in range(len(first)):
			if first[x][0] <= curmaxjump and first[x][1] > weight:
				weight = first[x][1]
				i = x
		if weight > 0:
			firstres += 1
			curmaxjump += weight
			first.pop(i)
		else:
			break
	else:
		break
	if len(second) > 0:
		i = 0
		weight = 0
		for x in range(len(second)):
			if second[x][0] <= curmaxjump and second[x][1] > weight:
				weight = second[x][1]
				i = x
		if weight > 0:
			firstres += 1
			curmaxjump += weight
			second.pop(i)
		else:
			break
	else:
		break
secondres = 0
curmaxjump = xx
first = copy.deepcopy(firstorig)
second = copy.deepcopy(secondorig)
while True:
	if len(second) > 0:
		i = 0
		weight = 0
		for x in range(len(second)):
			if second[x][0] <= curmaxjump and second[x][1] > weight:
				weight = second[x][1]
				i = x
		if weight > 0:
			secondres += 1
			curmaxjump += weight
			second.pop(i)
		else:
			break
	else:
		break
	if len(first) > 0:
		i = 0
		weight = 0
		for x in range(len(first)):
			if first[x][0] <= curmaxjump and first[x][1] > weight:
				weight = first[x][1]
				i = x
		if weight > 0:
			secondres += 1
			curmaxjump += weight
			first.pop(i)
		else:
			break
	else:
		break
print(max(firstres, secondres))


nw = input().split()
numCandies = int(nw[0])
weight = int(nw[1])
thm1 = []
thm2 = []
for i in range(numCandies):
	val = input().split()
	val = [int(x) for x in val]
	if val[0] == 0:
		thm1.append(val)
	else:
		thm2.append(val)

def get_candy(woc, tlist):
	ind = -1
	maxm = -1
	for k in range(len(tlist)):
		if tlist[k][1] <= woc:
			if maxm < tlist[k][2]:
				maxm = tlist[k][2]
				ind = k
	if ind >= 0:
		val1 = tlist.pop(ind)
		return val1
	return None
count = [0, 0]
for i in range(2):
	candyType = i
	initialWeight = weight
	thm1c = thm1[:]
	thm2c = thm2[:]
	while True:
		if candyType == 0:
			candy = get_candy(initialWeight, thm1c)
			if candy is not None:
				chm = candy
				h = chm[1]
				m = chm[2]
				initialWeight += m
				count[i] += 1
				candyType = 1
			else:
				break
		else:
			candy = get_candy(initialWeight, thm2c)
			if candy is not None:
				chm = candy
				h = chm[1]
				m = chm[2]
				initialWeight += m
				count[i] += 1
				candyType = 0
			else:
				break
print(max(count))


import itertools
import operator
(n, x) = map(int, str.split(input()))
a = []
b = []
for _ in range(n):
	(t, h, m) = map(int, str.split(input()))
	(a if t else b).append((h, m))
best = 0
for (ca, cb) in ((a, b), (b, a)):
	cx = x
	count = 0
	(ca, cb) = (ca[:], cb[:])
	while True:
		available = tuple(filter(lambda candy: candy[1][0] <= cx, enumerate(ca)))
		if available:
			(i, candy) = max(available, key=lambda candy: candy[1][1])
			ca.pop(i)
			count += 1
			cx += candy[1]
		else:
			break
		(ca, cb) = (cb, ca)
	best = max(best, count)
print(best)


from functools import cmp_to_key

def get_max_from(data, x):
	for (i, c) in enumerate(data):
		if c[0] <= x:
			data.pop(i)
			return c[1]
	return None

def test(data0, data1, x):
	total = 0
	while True:
		max_m = get_max_from(data0, x)
		if max_m is not None:
			x += max_m
			total += 1
		else:
			return total
		max_m = get_max_from(data1, x)
		if max_m is not None:
			x += max_m
			total += 1
		else:
			return total

def __starting_point():
	(n, x) = map(int, input().split())
	data0 = []
	data1 = []
	for i in range(n):
		d = tuple(map(int, input().split()))
		t = (d[1], d[2])
		if d[0] == 0:
			data0.append(t)
		else:
			data1.append(t)
	cmp = lambda a, b: b[1] - a[1]
	data0.sort(key=cmp_to_key(cmp))
	data1.sort(key=cmp_to_key(cmp))
	d0 = data0.copy()
	d1 = data1.copy()
	print(max(test(d0, d1, x), test(data1, data0, x)))
__starting_point()


(n, x) = map(int, input().split())
k = [[], []]

def add(s):
	(t, h, m) = map(int, s.split())
	k[t].append([h, m])
[add(input()) for _ in range(n)]

def calc(t):
	cur = x
	ans = 0
	mark = [[False] * len(k[0]), [False] * len(k[1])]
	while True:
		w = 0
		id = 0
		for i in range(len(k[t])):
			if mark[t][i] == False and w < k[t][i][1] and (cur >= k[t][i][0]):
				w = k[t][i][1]
				id = i
		if w == 0:
			break
		ans += 1
		cur += w
		mark[t][id] = True
		t = 1 - t
	return ans
sol = max(calc(0), calc(1))
print(sol)


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

class Candy:
	t = 0
	h = 0
	m = 0
candy0 = []
candy1 = []
for i in range(n):
	candy = Candy()
	(candy.t, candy.h, candy.m) = map(int, input().split())
	if candy.t == 0:
		candy0.append(candy)
	else:
		candy1.append(candy)

def sortfn(item):
	return item.m

def getnext(items, x):
	for item in items:
		if item.h <= x:
			return item
	val = Candy()
	val.h = x + 1
	return val
candy0.sort(key=sortfn, reverse=True)
candy1.sort(key=sortfn, reverse=True)
count0 = 0
count1 = 0

def getcount(candy0, candy1):
	count = 0
	next = candy0
	x = x1
	while getnext(next, x).h <= x:
		nextitem = getnext(next, x)
		x += nextitem.m
		count += 1
		next.remove(nextitem)
		if next == candy0:
			next = candy1
		else:
			next = candy0
	return count
count0 = getcount(candy0.copy(), candy1.copy())
count1 = getcount(candy1.copy(), candy0.copy())
print(max(count0, count1))


def solve(currentT):
	result = 0
	way = list(candy)
	bestCandy = -1
	flag = False
	for i in range(n):
		if way[i][0] == currentT:
			if way[i][1] <= x and (way[i][2] >= way[bestCandy][2] or bestCandy == -1):
				bestCandy = i
				flag = True
	if not flag:
		return 0
	power = x + way[bestCandy][2]
	result += 1
	flag = True
	while flag:
		temp = way.pop(bestCandy)
		bestCandy = -1
		currentT = 1 - currentT
		flag = False
		for i in range(len(way)):
			if way[i][0] == currentT:
				if way[i][1] <= power and (way[i][2] >= way[bestCandy][2] or bestCandy == -1):
					bestCandy = i
					flag = True
		if flag:
			power += way[bestCandy][2]
			result += 1
	return result
candy = []
(n, x) = tuple(map(int, input().split()))
for i in range(n):
	temp = list(map(int, input().split()))
	if temp[0] > 0:
		temp[0] = 1
	candy.append(temp)
candy = tuple(candy)
print(max(solve(0), solve(1)))


from copy import deepcopy

def getBetter(h, a):
	maxi = -1
	im = -1
	for i in range(len(a)):
		if h >= a[i][0]:
			if maxi < a[i][1]:
				im = i
				maxi = a[i][1]
	return (im, maxi)
(n, h0) = map(int, input().split())
lolipops0 = [[], []]
for i in range(n):
	(t, h, m) = map(int, input().split())
	lolipops0[t].append((h, m))
lolipops0[1].sort()
lolipops0[0].sort()
lolipops1 = deepcopy(lolipops0)
lol0 = getBetter(h0, lolipops0[0])
t1 = 0
h1 = h0
lol1 = getBetter(h0, lolipops0[1])
t2 = 1
h2 = h0
while lol0[0] >= 0 or lol1[0] >= 0:
	if lol0[0] > -1:
		if len(lolipops0[t1 % 2]) != 1 and lol0[0] != -1:
			lolipops0[t1 % 2].pop(lol0[0])
		else:
			lolipops0[t1 % 2] = []
		t1 += 1
		h1 += lol0[1]
		lol0 = getBetter(h1, lolipops0[t1 % 2])
	if lol1[0] > -1:
		if len(lolipops1[t2 % 2]) != 1 and lol1[0] != -1:
			lolipops1[t2 % 2].pop(lol1[0])
		else:
			lolipops1[t2 % 2] = []
		t2 += 1
		h2 += lol1[1]
		lol1 = getBetter(h2, lolipops1[t2 % 2])
print(max(t1, t2 - 1))