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.

Difficulty: competition

Starter code:

Solutions:
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)
    else:
        if 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))

#a, b, h, w, n = map(int,input().split())
#rash = map(int,input().split())
n, c, d = list(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)
#print(fon)

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
        else:
            if 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)


n,c,d = list(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)

    
    


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]
    #print(fnt)
    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
    else:
        if 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)

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)
    else:
        if 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)

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

import operator

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))
    else:
        if p <= d:
            fd.append((b, p))

fc.sort(key=operator.itemgetter(0), reverse=True)
fd.sort(key=operator.itemgetter(0), reverse=True)

mx = 0
if fc and fd:
    mx = fc[0][0] + fd[0][0]

for i in range(len(fc)):
    b1, p1 = fc[i]
    if 2 * b1 <= mx:
        break
    for j in range(i + 1, len(fc)):
        b2, p2 = fc[j]
        if b1 + b2 <= mx:
            break
        if p1 + p2 <= c:
            mx = b1 + b2
            break
        
for i in range(len(fd)):
    b1, p1 = fd[i]
    if 2 * b1 <= mx:
        break
    for j in range(i + 1, len(fd)):
        b2, p2 = fd[j]
        if b1 + b2 <= mx:
            break
        if p1 + p2 <= d:
            mx = b1 + b2
            break

print(mx)



import operator

def maxl(l, m, mx):
    for i in range(len(l) - 1):
        b1, p1 = l[i]
        if 2 * b1 <= 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))
    else:
        if p <= d:
            fd.append((b, p))

fc.sort(key=operator.itemgetter(0), reverse=True)
fd.sort(key=operator.itemgetter(0), reverse=True)

mx = 0
if fc and fd:
    mx = fc[0][0] + fd[0][0]

mx = maxl(fc, c, mx)
mx = maxl(fd, d, mx)

print(mx)



import operator

def maxl(l, m, mx):
    for i in range(len(l) - 1):
        b1, p1 = l[i]
        if 2 * b1 <= 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))
    else:
        if 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)


import operator

def maxl(l, m, mx):
    for i in range(len(l) - 1):
        b1, p1 = l[i]
        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))
    else:
        if 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)


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))
    else:
        if 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)


import operator

def maxl(l, m, mx):
    for i in range(len(l) - 1):
        b1, p1 = l[i]
        if b1 + b1 <= 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))
    else:
        if 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)


import operator

def maxl(l, m, mx):
    for i in range(len(l) - 1):
        b1, p1 = l[i]
        if b1 + b1 <= 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))
    else:
        if p <= d:
            fd.append((b, p))

fc.sort(key=operator.itemgetter(0), reverse=True)
fd.sort(key=operator.itemgetter(0), reverse=True)

mx = 0
if len(fc) and len(fd):
    mx = fc[0][0] + fd[0][0]
mx = maxl(fc, c, mx)
mx = maxl(fd, d, mx)

print(mx)


import operator

def maxl(l, m, mx):
    for i in range(len(l) - 1):
        b1, p1 = l[i]
        if b1 * 2 <= 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))
    else:
        if 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)


import operator

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))
    else:
        if 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

for l, m in ((fc, c), (fd, d)):
    for i in range(len(l) - 1):
        b1, p1 = l[i]
        if b1 * 2 <= 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

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)


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)


import operator

def maxl(l, m, mx):
    for i in range(len(l) - 1):
        b1, p1 = l[i]
        if b1 * 2 <= 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)
    f, cd = (fc, c) if m == 'C' else (fd, d)
    if p <= cd:
        f.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().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))


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
        else:
            if 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 = list(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 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
        else:
            if b > m1:
                m1, m2 = b, m1
            elif b > m2:
                m2 = b
    if m1 and m2 and m1 + m2 > mx:
         mx = m1 + m2
         
    lp = [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 = list(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 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), mb) in enumerate(zip(l, lb)):
        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 = list(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 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 = list(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 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 = list(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 = max(b for (b, p) in fc)
    bd = max(b for (b, p) in fd)
    mx = bc + bd
mx = maxl(fc, c, mx)
mx = maxl(fd, d, mx)

print(mx)