Arkady plays Gardenscapes a lot. Arkady wants to build two new fountains. There are n available fountains, for each fountain its beauty and cost are known. There are two types of money in the game: coins and diamonds, so each fountain cost can be either in coins or diamonds. No money changes between the types are allowed.

Help Arkady to find two fountains with maximum total beauty so that he can buy both at the same time.


-----Input-----

The first line contains three integers n, c and d (2 ≤ n ≤ 100 000, 0 ≤ c, d ≤ 100 000) — the number of fountains, the number of coins and diamonds Arkady has.

The next n lines describe fountains. Each of these lines contain two integers b_{i} and p_{i} (1 ≤ b_{i}, p_{i} ≤ 100 000) — the beauty and the cost of the i-th fountain, and then a letter "C" or "D", describing in which type of money is the cost of fountain i: in coins or in diamonds, respectively.


-----Output-----

Print the maximum total beauty of exactly two fountains Arkady can build. If he can't build two fountains, print 0.


-----Examples-----
Input
3 7 6
10 8 C
4 3 C
5 6 D

Output
9

Input
2 4 5
2 5 C
2 1 D

Output
0

Input
3 10 10
5 5 C
5 5 C
10 11 D

Output
10



-----Note-----

In the first example Arkady should build the second fountain with beauty 4, which costs 3 coins. The first fountain he can't build because he don't have enough coins. Also Arkady should build the third fountain with beauty 5 which costs 6 diamonds. Thus the total beauty of built fountains is 9.

In the second example there are two fountains, but Arkady can't build both of them, because he needs 5 coins for the first fountain, and Arkady has only 4 coins.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Sorting

Data structures

Implementation


Solutions:
import operator

def maxl(l, m, mx):
	for i in range(len(l) - 1):
		(b1, p1) = l[i]
		if b1 + l[i + 1][0] <= mx:
			break
		for j in range(i + 1, len(l)):
			(b2, p2) = l[j]
			if b1 + b2 <= mx:
				break
			if p1 + p2 <= m:
				mx = b1 + b2
				break
	return mx
fc = []
fd = []
(n, c, d) = list(map(int, input().split()))
for _ in range(n):
	(b, p, m) = input().split()
	(b, p) = (int(b), int(p))
	if m == 'C':
		if p <= c:
			fc.append((b, p))
	elif p <= d:
		fd.append((b, p))
fc.sort(key=operator.itemgetter(0), reverse=True)
fd.sort(key=operator.itemgetter(0), reverse=True)
mx = fc[0][0] + fd[0][0] if fc and fd else 0
mx = maxl(fc, c, mx)
mx = maxl(fd, d, mx)
print(mx)


(n, c, d) = list(map(int, input().strip().split(' ')))
import bisect
FC = []
FD = []
for _ in range(n):
	(A, B, C) = list(input().strip().split(' '))
	A = int(A)
	B = int(B)
	if C == 'C':
		if B <= c:
			FC += [[int(A), int(B)]]
	elif B <= d:
		FD += [[int(A), int(B)]]
MAXcd = 0
if len(FC) >= 1 and len(FD) >= 1:
	MAXc = 0
	for i in range(len(FC)):
		if FC[i][0] > MAXc:
			MAXc = FC[i][0]
	MAXd = 0
	for i in range(len(FD)):
		if FD[i][0] > MAXd:
			MAXd = FD[i][0]
	MAXcd = MAXc + MAXd

def find(FC, c):
	if len(FC) <= 1:
		return 0
	rFC = [[FC[i][1], FC[i][0], i] for i in range(len(FC))]
	rFC = sorted(rFC)
	cost = [rFC[i][0] for i in range(len(rFC))]
	if rFC[0][0] + rFC[1][0] > c:
		return 0
	MAXc = rFC[0][1] + rFC[1][1]
	counting = []
	MAX = rFC[0][1]
	counting += [MAX]
	for i in range(1, len(rFC)):
		if rFC[i][1] > MAX:
			MAX = rFC[i][1]
		counting += [MAX]
	for i in range(1, len(rFC)):
		ans = rFC[i][1]
		temp = rFC[i][0]
		position = bisect.bisect_right(cost, min(temp - 1, c - temp)) - 1
		if position != -1:
			ans += counting[position]
		if ans > MAXc and position != -1:
			MAXc = ans
	COUNT = [[] for i in range(100001)]
	for i in range(len(rFC)):
		COUNT[rFC[i][0]] += [rFC[i][1]]
	for i in range(0, len(COUNT)):
		if 2 * i <= c:
			if len(COUNT[i]) >= 2:
				COUNT[i] = sorted(COUNT[i])
				ans = COUNT[i][-1] + COUNT[i][-2]
				if ans > MAXc:
					MAXc = ans
	return MAXc
MAXc = find(FC, c)
MAXd = find(FD, d)
print(max(MAXcd, MAXc, MAXd))


import operator
import itertools
import bisect

def maxl(l, m, mx):
	l.sort(key=operator.itemgetter(1))
	lp = [p for (b, p) in l]
	lb = list(itertools.accumulate((b for (b, p) in l), max))
	for (i, (b, p)) in enumerate(l):
		k = bisect.bisect_right(lp, m - p, 0, i)
		if k:
			x = b + lb[k - 1]
			if x > mx:
				mx = x
	return mx
fc = []
fd = []
(n, c, d) = map(int, input().split())
for _ in range(n):
	(b, p, m) = input().split()
	(b, p) = (int(b), int(p))
	(f, cd) = (fc, c) if m == 'C' else (fd, d)
	if p <= cd:
		f.append((b, p))
mx = 0
if fc and fd:
	(bc, pc) = max(fc, key=operator.itemgetter(0))
	(bd, pd) = max(fd, key=operator.itemgetter(0))
	mx = bc + bd
mx = maxl(fc, c, mx)
mx = maxl(fd, d, mx)
print(mx)


import math
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

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

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater
(n, c, dw) = map(int, input().split())
d = []
d1 = []
for i in range(n):
	(a, b, c1) = map(str, input().split())
	if c1 == 'C':
		d.append((int(b), int(a)))
	else:
		d1.append((int(b), int(a)))
d.sort()
d1.sort()
ans = 0
l = []
l1 = []
val = []
val1 = []
beau = []
beau1 = []
m = 0
m1 = 0
for i in range(len(d)):
	if d[i][0] <= c:
		l.append(d[i])
		val.append(d[i][0])
		beau.append(d[i][1])
		m = max(d[i][1], m)
	else:
		break
for i in range(len(d1)):
	if d1[i][0] <= dw:
		l1.append(d1[i])
		val1.append(d1[i][0])
		beau1.append(d1[i][1])
		m1 = max(m1, d1[i][1])
	else:
		break
if m != 0 and m1 != 0:
	ans = m + m1
s = SegmentTree(beau)
s1 = SegmentTree(beau1)
for i in range(len(l)):
	rem = c - l[i][0]
	m = binarySearchCount(val, len(val), rem)
	if m == 0 or i == 0:
		continue
	ans = max(ans, l[i][1] + s.query(0, min(i - 1, m - 1)))
for i in range(len(l1)):
	rem = dw - l1[i][0]
	m = binarySearchCount(val1, len(val1), rem)
	if m == 0 or i == 0:
		continue
	ans = max(ans, l1[i][1] + s1.query(0, min(i - 1, m - 1)))
print(ans)


from sys import stdin, stdout

def rint():
	return map(int, stdin.readline().split())
(n, c, d) = rint()

def mt(T, index, a):
	maxb0 = 0
	maxb1 = 0
	for (i, j) in enumerate(a):
		(p, b) = j
		if maxb0 < b:
			maxb1 = maxb0
			maxb0 = b
			index[i] = i
		elif maxb1 < b:
			maxb1 = b
			index[i] = index[i - 1]
		else:
			index[i] = index[i - 1]
		T[i][0] = maxb0
		T[i][1] = maxb1

def findmax(T, a, c, index):
	maxb = 0
	if len(a) == 0:
		return 0
	for (i, j) in enumerate(a):
		(p, b) = j
		if c - p <= 0:
			break
		i2 = findai(a, c - p)
		if i2 == -1:
			continue
		if i == index[i2]:
			bb = T[i2][1]
		else:
			bb = T[i2][0]
		if bb == 0:
			b = 0
		maxb = max(maxb, bb + b)
	return maxb

def findai(a, p):
	s = 0
	e = len(a)
	if a[0][0] > p:
		return -1
	while e - s > 1:
		i = (s + e) // 2
		if a[i][0] <= p:
			s = i
		else:
			e = i
	return s
a = []
b = []
for i in range(n):
	(bb, pp, tt) = input().split()
	bb = int(bb)
	pp = int(pp)
	if tt == 'C':
		a.append([pp, bb])
	else:
		b.append([pp, bb])
la = len(a)
lb = len(b)
a.sort()
b.sort()
TA = [[0, 0] for i in range(la)]
TB = [[0, 0] for i in range(lb)]
TAi = [-1 for i in range(la)]
TBi = [-1 for i in range(lb)]
mt(TA, TAi, a)
mt(TB, TBi, b)
ci = -1
di = -1
if len(a):
	ci = findai(a, c)
if len(b):
	di = findai(b, d)
if ci == -1 or di == -1:
	cd = 0
else:
	cd = TA[ci][0] + TB[di][0]
ans = max(findmax(TA, a, c, TAi), findmax(TB, b, d, TBi), cd)
print(ans)


def get_max(arr, m, curr_max):
	for i in range(len(arr) - 1):
		(b1, p1) = arr[i]
		if 2 * b1 <= curr_max:
			break
		for j in range(i + 1, len(arr)):
			(b2, p2) = arr[j]
			if b1 + b2 <= curr_max:
				break
			if p1 + p2 <= m:
				curr_max = b1 + b2
				break
	return curr_max
(fd, fc) = ([], [])
(n, c, d) = map(int, input().split())
for _ in range(n):
	(b, p, m) = input().split()
	(b, p) = (int(b), int(p))
	if m == 'C':
		if p <= c:
			fc.append((b, p))
	elif p <= d:
		fd.append((b, p))
fc = sorted(fc, reverse=True)
fd = sorted(fd, reverse=True)
res = fc[0][0] + fd[0][0] if fc and fd else 0
res = get_max(fc, c, res)
res = get_max(fd, d, res)
print(res)


(n, c, d) = list(map(int, input().split()))
coin = []
diamond = []
for i in range(n):
	tmp = input().split()
	if tmp[-1] == 'C' and int(tmp[1]) <= c:
		coin.append(list(map(int, tmp[:2])))
	if tmp[-1] == 'D' and int(tmp[1]) <= d:
		diamond.append(list(map(int, tmp[:2])))
res1 = 0
mc = -float('inf')
for i in coin:
	if mc < i[0] and i[1] <= c:
		mc = i[0]
md = -float('inf')
for i in diamond:
	if md < i[0] and i[1] <= d:
		md = i[0]
if mc != -float('inf') and md != -float('inf'):
	res1 = md + mc
coin.sort(key=lambda x: x[1], reverse=True)
diamond.sort(key=lambda x: x[1], reverse=True)
prefc = [0 for i in range(len(coin))]
prefd = [0 for i in range(len(diamond))]
if len(coin):
	prefc[-1] = coin[-1][0]
if len(diamond):
	prefd[-1] = diamond[-1][0]
for i in range(len(coin) - 2, -1, -1):
	prefc[i] = max(prefc[i + 1], coin[i][0])
for i in range(len(diamond) - 2, -1, -1):
	prefd[i] = max(prefd[i + 1], diamond[i][0])
res2 = 0
res3 = res2
for i in range(len(coin)):
	p = c - coin[i][1]
	l = i
	r = len(coin) - 1
	while r - l > 1:
		m = (r + l) // 2
		if coin[m][1] > p:
			l = m
		else:
			r = m
	if coin[r][1] <= p and r > i:
		res2 = max(res2, coin[i][0] + prefc[r])
for i in range(len(diamond)):
	p = d - diamond[i][1]
	l = i
	r = len(diamond) - 1
	while r - l > 1:
		m = (r + l) // 2
		if diamond[m][1] > p:
			l = m
		else:
			r = m
	if diamond[r][1] <= p and r > i:
		res3 = max(res3, diamond[i][0] + prefd[r])
print(max(res1, res2, res3))


def main():
	fountains_c = []
	fountains_d = []
	(n, coins, diamonds) = [int(x) for x in input().split()]
	for _ in range(n):
		(beauty, cost, type) = input().split()
		beauty = int(beauty)
		cost = int(cost)
		if type == 'C':
			if cost > coins:
				continue
			fountains_c.append((beauty, cost))
		elif type == 'D':
			if cost > diamonds:
				continue
			fountains_d.append((beauty, cost))
		else:
			raise Exception('Invalid type')
	fountains_c = sorted(fountains_c, key=lambda tup: tup[0], reverse=True)
	fountains_d = sorted(fountains_d, key=lambda tup: tup[0], reverse=True)
	n_c = len(fountains_c)
	n_d = len(fountains_d)
	max_beauty = 0
	if n_c == 0 and n_d == 0:
		return 0
	if n_c > 0 and n_d > 0:
		max_beauty = fountains_c[0][0] + fountains_d[0][0]
	for i in range(n_c - 1):
		for j in range(i + 1, n_c):
			if fountains_c[i][0] + fountains_c[j][0] <= max_beauty:
				break
			if fountains_c[i][1] + fountains_c[j][1] <= coins:
				assert fountains_c[i][0] + fountains_c[j][0] > max_beauty
				max_beauty = fountains_c[i][0] + fountains_c[j][0]
				break
	for i in range(n_d - 1):
		for j in range(i + 1, n_d):
			if fountains_d[i][0] + fountains_d[j][0] <= max_beauty:
				break
			if fountains_d[i][1] + fountains_d[j][1] <= diamonds:
				assert fountains_d[i][0] + fountains_d[j][0] > max_beauty
				max_beauty = fountains_d[i][0] + fountains_d[j][0]
				break
	return max_beauty
print(main())


import operator
import itertools
import bisect

def maxl(l, m, mx):
	l.sort(key=operator.itemgetter(1))
	(m1, m2) = (0, 0)
	pp = None
	for (b, p) in l:
		if p != pp:
			if 2 * p > m:
				break
			if m1 and m2 and (m1 + m2 > mx):
				mx = m1 + m2
			(m1, m2) = (b, 0)
			pp = p
		elif b > m1:
			(m1, m2) = (b, m1)
		elif b > m2:
			m2 = b
	if m1 and m2 and (m1 + m2 > mx):
		mx = m1 + m2
	lp = list((p for (b, p) in l))
	lb = list(itertools.accumulate((b for (b, p) in l), max))
	for (i, ((b, p), mb)) in enumerate(zip(l, lb)):
		p1 = min(m - p, p - 1)
		k = bisect.bisect_right(lp, p1, 0, i)
		if k:
			x = b + lb[k - 1]
			if x > mx:
				mx = x
	return mx
fc = []
fd = []
(n, c, d) = map(int, input().split())
for _ in range(n):
	(b, p, m) = input().split()
	(b, p) = (int(b), int(p))
	(f, cd) = (fc, c) if m == 'C' else (fd, d)
	if p <= cd:
		f.append((b, p))
mx = 0
if fc and fd:
	(bc, pc) = max(fc, key=operator.itemgetter(0))
	(bd, pd) = max(fd, key=operator.itemgetter(0))
	mx = bc + bd
mx = maxl(fc, c, mx)
mx = maxl(fd, d, mx)
print(mx)


from operator import itemgetter

def get_one_max(arr, resource):
	res = 0
	for (beauty, _) in [x for x in arr if x[1] <= resource]:
		res = max(res, beauty)
	return res

def get_two_max(arr, resource):
	arr.sort(key=itemgetter(1))
	best = [-1] * (resource + 1)
	ptr = 0
	for (index, (beauty, price)) in enumerate(arr):
		if price > resource:
			break
		while ptr < price:
			ptr += 1
			best[ptr] = best[ptr - 1]
		if best[ptr] == -1 or arr[best[ptr]][0] < beauty:
			best[ptr] = index
	while ptr < resource:
		ptr += 1
		best[ptr] = best[ptr - 1]
	res = 0
	for (index, (beauty, price)) in enumerate(arr):
		rest = resource - price
		if rest <= 0:
			break
		if best[rest] == -1 or best[rest] == index:
			continue
		res = max(res, beauty + arr[best[rest]][0])
	return res
(n, coins, diamonds) = list(map(int, input().split()))
with_coins = []
with_diamonds = []
for i in range(n):
	(beauty, price, tp) = input().split()
	if tp == 'C':
		with_coins.append((int(beauty), int(price)))
	else:
		with_diamonds.append((int(beauty), int(price)))
with_coins_max = get_one_max(with_coins, coins)
with_diamonds_max = get_one_max(with_diamonds, diamonds)
ans = 0 if with_coins_max == 0 or with_diamonds_max == 0 else with_coins_max + with_diamonds_max
ans = max(ans, get_two_max(with_coins, coins))
ans = max(ans, get_two_max(with_diamonds, diamonds))
print(ans)


(n, c, d) = map(int, input().split())
fon = []
for i in range(n):
	s = input().split()
	kras = int(s[0])
	ctoim = int(s[1])
	if s[2] == 'C':
		fon.append([kras, ctoim, True])
	else:
		fon.append([kras, ctoim, False])

def sravni(elem):
	return elem[0]
fon.sort(key=sravni, reverse=True)
maxkras = 0
for fon1 in range(n):
	tekc = c
	tekd = d
	if fon[fon1][2]:
		tekc -= fon[fon1][1]
	else:
		tekd -= fon[fon1][1]
	if tekc < 0 or tekd < 0:
		continue
	fon2 = -1
	for i in range(fon1 + 1, n):
		if fon[i][2]:
			if fon[i][1] <= tekc:
				fon2 = i
				break
		elif fon[i][1] <= tekd:
			fon2 = i
			break
	if not fon2 == -1:
		if fon[fon1][0] + fon[fon2][0] > maxkras:
			maxkras = fon[fon1][0] + fon[fon2][0]
print(maxkras)


import sys
import math
from collections import defaultdict, deque
import heapq
(n, c, d) = map(int, sys.stdin.readline().split())
coin = []
dia = []
coins = []
dias = []
(cc, cd) = (0, 0)
for i in range(n):
	(a, b, e) = list(sys.stdin.readline().split())
	if e == 'C':
		coin.append([int(b), int(a), cc])
		cc += 1
		coins.append(int(a))
	if e == 'D':
		dia.append([int(b), int(a), cd])
		cd += 1
		dias.append(int(a))
coin.sort()
dia.sort()
bc = -1
n = len(coin)
nax = -1
for i in range(n):
	nax = max(nax, coin[i][1])
	coin[i][1] = nax
	if coin[i][0] <= c:
		bc = coin[i][1]
n = len(dia)
bd = -1
nax = -1
for i in range(n):
	nax = max(nax, dia[i][1])
	dia[i][1] = nax
	if dia[i][0] <= d:
		bd = dia[i][1]
curb = 0
if bc != -1 and bd != -1:
	curb = bc + bd
n = len(coin)
for i in range(n):
	low = 0
	high = i - 1
	rem = c - coin[i][0]
	xb = coins[coin[i][2]]
	newb = -1
	while low <= high:
		mid = (low + high) // 2
		if coin[mid][0] <= rem:
			newb = max(newb, coin[mid][1])
			low = mid + 1
		else:
			high = mid - 1
	if newb != -1:
		curb = max(curb, xb + newb)
n = len(dia)
for i in range(n):
	low = 0
	high = i - 1
	rem = d - dia[i][0]
	xb = dias[dia[i][2]]
	newb = -1
	while low <= high:
		mid = (low + high) // 2
		if dia[mid][0] <= rem:
			newb = max(newb, dia[mid][1])
			low = mid + 1
		else:
			high = mid - 1
	if newb != -1:
		curb = max(curb, xb + newb)
print(curb)


from bisect import *
(n, tc, td) = [int(i) for i in input().split()]
fc = []
fd = []
mbc = 0
mbd = 0
for _ in range(n):
	(b, p, ft) = input().split()
	(b, p) = (int(b), int(p))
	f = (p, b)
	if ft == 'C':
		if p <= tc:
			fc.append(f)
			mbc = max(mbc, b)
	elif p <= td:
		fd.append(f)
		mbd = max(mbd, b)
fc = sorted(fc)
fd = sorted(fd)

def pick2(fc, tc):
	bf = []
	maxb = 0
	ans = 0
	for f in fc:
		(p, b) = f
		maxpp = tc - p
		ii = bisect_left(bf, (maxpp + 1, 0)) - 1
		if ii >= 0:
			(pp, bb) = bf[ii]
			ans = max(ans, bb + b)
		if b > maxb:
			bf.append(f)
			maxb = b
	return ans
ans = mbc + mbd if mbc > 0 and mbd > 0 else 0
ans = max(ans, pick2(fc, tc))
ans = max(ans, pick2(fd, td))
print(ans)


(n, c, d) = map(int, input().split())
inf = 10 ** 9
a = [0] * n
sc = []
sd = []
for i in range(n):
	(b, p, t) = input().split()
	b = int(b)
	p = int(p)
	a[i] = [b, p, t]
	if t == 'C':
		sc.append([p, b])
	else:
		sd.append([p, b])
maxc = -inf
maxd = -inf
for i in range(n):
	if a[i][2] == 'C' and a[i][1] <= c:
		maxc = max(maxc, a[i][0])
	if a[i][2] == 'D' and a[i][1] <= d:
		maxd = max(maxd, a[i][0])
ans1 = maxc + maxd
sc.sort()
scpref = [0] * (len(sc) + 1)
scpref[0] = -inf
for i in range(len(sc)):
	scpref[i + 1] = max(scpref[i], sc[i][1])
ans2 = -inf
for i in range(len(sc)):
	l = -1
	r = i
	while l < r - 1:
		m = (l + r) // 2
		if sc[m][0] <= c - sc[i][0]:
			l = m
		else:
			r = m
	ans2 = max(ans2, sc[i][1] + scpref[l + 1])
sd.sort()
sdpref = [0] * (len(sd) + 1)
sdpref[0] = -inf
for i in range(len(sd)):
	sdpref[i + 1] = max(sdpref[i], sd[i][1])
ans3 = -inf
for i in range(len(sd)):
	l = -1
	r = i
	while l < r - 1:
		m = (l + r) // 2
		if sd[m][0] <= d - sd[i][0]:
			l = m
		else:
			r = m
	ans3 = max(ans3, sd[i][1] + sdpref[l + 1])
ans = max(ans1, ans2, ans3)
print(max(ans, 0))


from bisect import *

def pair(fc, tc):
	bf = []
	maxb = 0
	ans = 0
	for f in fc:
		(p, b) = f
		maxpp = tc - p
		ii = bisect_left(bf, (maxpp + 1, 0)) - 1
		if ii >= 0:
			(pp, bb) = bf[ii]
			ans = max(ans, bb + b)
		if b > maxb:
			bf.append(f)
			maxb = b
	return ans
(n, c, d) = map(int, input().split())
arr1 = []
arr2 = []
for i in range(n):
	(b, k, t) = input().split()
	(b, k) = (int(b), int(k))
	if t == 'C' and k <= c:
		arr1.append((k, b))
	if t == 'D' and k <= d:
		arr2.append((k, b))
if len(arr1) > 0 and len(arr2) > 0:
	v1 = max(arr1, key=lambda x: x[1])[1] + max(arr2, key=lambda x: x[1])[1]
else:
	v1 = 0
v2 = pair(sorted(arr1), c)
v3 = pair(sorted(arr2), d)
print(max([v1, v2, v3]))


(n, c, d) = map(int, input().split())
a = []
inf = 10 ** 10
for i in range(n):
	a.append(input().split())
	(a[i][0], a[i][1]) = (int(a[i][0]), int(a[i][1]))

def tr(r, s, have):
	if len(r) < 2:
		return 0
	mn = [0] * len(r)
	mn[0] = r[0][1]
	for i in range(len(r)):
		mn[i] = max(r[i][1], mn[i - 1])
	p = -1
	rs = -inf
	for i in range(len(r) - 1, -1, -1):
		while p + 1 < i and r[p + 1][0] <= have - r[i][0]:
			p += 1
		if p != -1:
			if p >= i:
				if i:
					rs = max(rs, mn[i - 1] + r[i][1])
			else:
				rs = max(rs, mn[p] + r[i][1])
	return rs
ans = 0
cmx = 0
dmx = 0
for i in range(n):
	if a[i][2] == 'C' and a[i][1] <= c:
		cmx = max(cmx, a[i][0])
	elif a[i][1] <= d:
		dmx = max(dmx, a[i][0])
if cmx > 0 and dmx > 0:
	ans = max(ans, cmx + dmx)
dm = []
for i in range(len(a)):
	if a[i][2] == 'C':
		dm.append((a[i][1], a[i][0]))
dm.sort()
ans = max(ans, tr(dm, 'C', c))
dm = []
for i in range(len(a)):
	if a[i][2] == 'D':
		dm.append((a[i][1], a[i][0]))
dm.sort()
ans = max(ans, tr(dm, 'D', d))
if ans == -inf:
	print(0)
else:
	print(ans)


from copy import deepcopy
from bisect import *
(n, c, d) = map(int, input().split())
bb = [c, d]
arr = [[], []]
for i in range(n):
	(b, x, t) = input().split()
	b = int(b)
	x = int(x)
	if t == 'C':
		arr[0].append((x, b))
	else:
		arr[1].append((x, b))
arr[0].sort()
arr[1].sort()
mxs = [[0] * len(arr[i]) for i in range(2)]
for j in range(2):
	cur = [-1, -1]
	for i in range(len(arr[j])):
		if cur[0] < 0 or arr[j][cur[0]][1] < arr[j][i][1]:
			cur[0] = i
		elif cur[1] < 0 or arr[j][cur[1]][1] < arr[j][i][1]:
			cur[1] = i
		mxs[j][i] = deepcopy(cur)
ans = 0
for j in range(2):
	for i in range(len(arr[j])):
		k = bisect_right(arr[j], (bb[j] - arr[j][i][0], float('inf')))
		if k == 0:
			continue
		o = mxs[j][k - 1][0]
		if o == i:
			o = mxs[j][k - 1][1]
		if o >= 0:
			ans = max(ans, arr[j][o][1] + arr[j][i][1])
dif = [-1, -1]
for j in range(2):
	for i in range(len(arr[j])):
		if arr[j][i][0] > bb[j]:
			break
		dif[j] = max(dif[j], arr[j][i][1])
if dif[0] >= 0 and dif[1] >= 0:
	ans = max(ans, sum(dif))
print(ans)


(n, t, d) = map(int, input().split())
coin = [[(0, 0), (0, 0)] for i in range(100001)]
diam = [[(0, 0), (0, 0)] for i in range(100001)]
f = []
for i in range(n):
	(b, c, q) = input().split()
	b = int(b)
	c = int(c)
	if q == 'C':
		f.append((b, c, 1))
		if coin[c][0][0] < b:
			coin[c][1] = coin[c][0]
			coin[c][0] = (b, i)
		elif coin[c][1][0] < b:
			coin[c][1] = (b, i)
	else:
		f.append((b, c, 2))
		if diam[c][0][0] < b:
			diam[c][1] = diam[c][0]
			diam[c][0] = (b, i)
		elif diam[c][1][0] < b:
			diam[c][1] = (b, i)
for i in range(2, 100001):
	if coin[i][0][0] < coin[i - 1][0][0]:
		coin[i][1] = max(coin[i][0], coin[i - 1][1])
		coin[i][0] = coin[i - 1][0]
	else:
		coin[i][1] = max(coin[i - 1][1], coin[i][1])
	if diam[i][0][0] < diam[i - 1][0][0]:
		diam[i][1] = max(diam[i][0], diam[i - 1][1])
		diam[i][0] = diam[i - 1][0]
	else:
		diam[i][1] = max(diam[i - 1][1], diam[i][1])
p = False
ans = 0
for i in range(n):
	fnt = f[i]
	if fnt[2] == 1:
		if t >= fnt[1]:
			s = t - fnt[1]
			if coin[s][0][0] > 0 and coin[s][0][1] != i:
				ans = max(fnt[0] + coin[s][0][0], ans)
				p = True
			elif coin[s][1][0] > 0:
				ans = max(fnt[0] + coin[s][1][0], ans)
				p = True
			if diam[d][0][0] > 0:
				ans = max(fnt[0] + diam[d][0][0], ans)
				p = True
	elif d >= fnt[1]:
		s = d - fnt[1]
		if diam[s][0][0] > 0 and diam[s][0][1] != i:
			ans = max(fnt[0] + diam[s][0][0], ans)
			p = True
		elif diam[s][1][0] > 0:
			ans = max(fnt[0] + diam[s][1][0], ans)
			p = True
		if coin[t][0][0] > 0:
			ans = max(fnt[0] + coin[t][0][0], ans)
			p = True
if p:
	print(ans)
else:
	print(0)


import sys
from operator import itemgetter
from bisect import bisect
inf = 1 << 30

def solve():
	(n, c, d) = map(int, input().split())
	cs = []
	ds = []
	b = [0] * n
	p = [0] * n
	for i in range(n):
		(bi, pi, ti) = sys.stdin.readline().split()
		bi = int(bi)
		pi = int(pi)
		b[i] = bi
		p[i] = pi
		if ti == 'C':
			cs.append((pi, bi, i))
		else:
			ds.append((pi, bi, i))
	cs.sort()
	ds.sort()
	fc = [[-1] * 2 for i in range(c + 1)]
	fd = [[-1] * 2 for i in range(d + 1)]
	lc = 0
	for w in range(1, c + 1):
		fc[w] = fc[w - 1][:]
		if lc < len(cs) and w == cs[lc][0]:
			for j in range(lc, len(cs)):
				if cs[j][0] > w:
					lc = j
					break
				if fc[w][0] == -1 or cs[j][1] > b[fc[w][0]]:
					(fc[w][0], fc[w][1]) = (cs[j][2], fc[w][0])
				elif fc[w][1] == -1 or cs[j][1] > b[fc[w][1]]:
					fc[w][1] = cs[j][2]
			else:
				lc = len(cs)
	ld = 0
	for w in range(1, d + 1):
		fd[w] = fd[w - 1][:]
		if ld < len(ds) and w == ds[ld][0]:
			for j in range(ld, len(ds)):
				if ds[j][0] > w:
					ld = j
					break
				if fd[w][0] == -1 or ds[j][1] > b[fd[w][0]]:
					(fd[w][0], fd[w][1]) = (ds[j][2], fd[w][0])
				elif fd[w][1] == -1 or ds[j][1] > b[fd[w][1]]:
					fd[w][1] = ds[j][2]
			else:
				ld = len(ds)
	ans = 0
	if fc[c][0] != -1 and fd[d][0] != -1:
		ans = max(ans, b[fc[c][0]] + b[fd[d][0]])
	for (cpi, cbi, i) in cs:
		if c - cpi <= 0:
			break
		if fc[c - cpi][0] != -1:
			if fc[c - cpi][0] != i:
				ans = max(ans, b[i] + b[fc[c - cpi][0]])
			elif fc[c - cpi][1] != -1:
				ans = max(ans, b[i] + b[fc[c - cpi][1]])
		else:
			break
	for (dpi, dbi, i) in ds:
		if d - dpi <= 0:
			break
		if fd[d - dpi][0] != -1:
			if fd[d - dpi][0] != i:
				ans = max(ans, b[i] + b[fd[d - dpi][0]])
			elif fd[d - dpi][1] != -1:
				ans = max(ans, b[i] + b[fd[d - dpi][1]])
		else:
			break
	print(ans)
solve()