(Codeforces Round #413, rated, Div. 1 + Div. 2) C. Fountains 线段树

C. Fountains

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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 bi and pi (1 ≤ bi, pi ≤ 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

Copy

Output

Copy

Input

Copy

2 4 5
2 5 C
2 1 D

Output

Copy

Input

Copy

Output

Copy

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.

题意：要求建两个喷泉，现在有n个喷泉可以选，每一个喷泉的价格和漂亮度都已经给出，这里有两种货币，硬币和钻石，所以每一个喷泉只能用这两个货币中的一种购买。求出他能建的喷泉的方法中最大的漂亮度。

要建两个喷泉，一共就三种情况，选一个用硬币买的喷泉再选一个用钻石买的喷泉，或者选两个用硬币买的喷泉，或者选两个用钻石买的喷泉。

借鉴模板，用线段树解决

枚举第一个喷泉，再在其他可以选的喷泉里找一个漂亮度最大的

#include<bits/stdc++.h>
using namespace std;
/*
这里维护的是最大值
类：IntervalTree
IntervalTree(size)  构造一棵维护区间【1--size】的线段树
int Query(a,b)  [a,b]最大值
Modify(a,d)  把第a 个元素改成 d;
*/

#define TREE_SIZE (1<<(20))
class IntervalTree{
private:
    int Cover[TREE_SIZE],Top[TREE_SIZE];
    int size;
    int _Query(int a,int b,int l,int r,int Ind)
    {
        if(a<=l&&b>=r)
            return Top[Ind];
        int mid=(l+r)>>1,ret=Cover[Ind];
        if(a<=mid)
            ret=max(ret,_Query(a,b,l,mid,Ind<<1));
        if(b>mid)
            ret=max(ret,_Query(a,b,mid+1,r,(Ind<<1)+1));
        return ret;
    }
    void _Modify(int a,int l,int r,int Ind,int d)
    {
        if(l==r&&l==a)
        {
            Cover[Ind]=Top[Ind]=d;
            return ;
        }
        int mid=(l+r)>>1;
        if(a<=mid)
            _Modify(a,l,mid,(Ind<<1),d);
        else
            _Modify(a,mid+1,r,(Ind<<1)+1,d);
        Top[Ind]=max(Top[Ind<<1],Top[(Ind<<1)+1]);
    }

public:
    IntervalTree()
    {
        memset(Cover,0,sizeof(Cover));
        memset(Top,0,sizeof(Top));
        size=(TREE_SIZE>>2)-1;
    }
    IntervalTree(int size):size(size)
    {
        memset(Cover,0,sizeof(Cover));
        memset(Top,0,sizeof(Top));
    }
    int Query(int a,int b)
    {
        return _Query(a,b,1,size,1);
    }
    void Modify(int a,int d)
    {
        return _Modify(a,1,size,1,d);
    }
};


IntervalTree _coi(100000<<2);
IntervalTree _dia(100000<<2);
int main()
{
int n,coin,dia;
int bea;
int cost;
char s[5];
int ans=0;

cin>>n>>coin>>dia;
for(int i=1;i<=n;i++)
{
scanf("%d%d%s",&bea,&cost,s);
if(s[0]=='C')//全  硬币
{
    if(cost>coin)
        continue;
   else if(cost<coin)
   {
if(_coi.Query(1,coin-cost))
    ans=max(ans,bea+_coi.Query(1,coin-cost));
   }

    _coi.Modify(cost,max(_coi.Query(1,cost),bea));

}
else if(s[0]=='D')  //全钻石
{
     if(cost>dia)
        continue;
    else if(cost<dia)
    {
if(_dia.Query(1,dia-cost))
       ans=max(ans,bea+_dia.Query(1,dia-cost));
    }
    _dia.Modify(cost,max(_dia.Query(1,cost),bea));

}

}
int x=_coi.Query(1,coin);
int y=_dia.Query(1,dia);// 一个硬币 一个钻石
if(x&&y)
ans=max(ans,x+y);
printf("%d",ans);


}