Fountains
某土豪想要造两座喷泉。现在有 n 个造喷泉的方案，我们已知每个方案的价格以及美观度。有两种合法的货币：金币和钻石。这两种货币之间不能以任何方式转换。
找出一种合法方案使得两座喷泉的美观度和最大。
Input
第一行包含 3 个整数 n, c 和 d (2 ≤ n ≤ 100 000, 0 ≤ c, d ≤ 100 000) — 表示造喷泉的方案数，金币的数量和钻石的数量。
之后 n 行描述每一种建造喷泉的方案。每行包含两个整数 bi 和 pi (1 ≤ bi, pi ≤ 100 000) — 分别表示第 i 个喷泉的美观度和价格，之后一个字符”C” 或 “D”， 表示这个价格使用金币还是钻石描述的。
Output
输出两个美观度最大的喷泉的美观度和。如果没有合法方案，输出 0.
Example
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
第一个样例中造第2个喷泉，美观度为 4, 价格为 3 金币。第一个喷泉没有足够的金币来造。同时还造第3个喷泉，美观度为 5 ，价格为 6 钻石。那么总美观度为 9。
第二个样例中没有合法方案。
可以预处理出
pre1[N][2]
表示花费N个金币,能够获得的最大美丽值和次小美丽值;
然后对以下3种情况枚举其中的一个;
一.
两个商品都是金币买的
则枚举其中一个商品是哪一个;
然后看看余额还剩多少->rest;
直接获取pre1[rest][0]
如果枚举的商品的价格<=rest且pre1[rest][0]和这个枚举的商品的美丽值一样
就取pre1[rest][1];即次小值;
二.
两个商品都是钻石买的，同上
三.
一个商品是钻石买的，另外一个是金币买的，各自单独找最大值；
#include <bits/stdc++.h>
#define rep1(i,x,y) for(int i=x;i<=y;i++)
#define rep2(i,x,y) for(int i=y;i>=x;i--)
#define pb push_back
#define long long ll
using namespace std;
const int N=2e5+100;struct node
{
int b;//beauty
int p;//price
int id;
};
vector<int> g[2][N];//the beauty of two types fountain from each price
int bo[2][N][2];
int n,c,d;
node a[N];
int main()
{
ios_base::sync_with_stdio(0);
cin>>n>>c>>d;
char s[3];
rep1(i,1,n)
{
cin>>a[i].b>>a[i].p;
cin>>s;
a[i].id=(s[0]=='C') ? 0:1;
g[a[i].id][a[i].p].pb(a[i].b);
}
rep1(k,0,1)
{
rep1(i,1,100000)
{
bo[k][i][1]=bo[k][i-1][1];//DP
bo[k][i][0]=bo[k][i-1][0];//DP
int len=g[k][i].size();
rep1(j,0,len-1)
{
if(g[k][i][j]>bo[k][i][0])
{//g[k(*id)][i(*price)][j(*beauty)]
bo[k][i][1]=bo[k][i][0];
bo[k][i][0]=g[k][i][j];
//bo[k][i][0] find the best beauty and
//bo[k][i][0] the second beauty
//of fountains in the same price by coins
//(or diamonds,depends on "k")
}
else if(g[k][i][j]>bo[k][i][1])
bo[k][i][1]=g[k][i][j];
}
}
}
//all coins
int ans=0;
rep1(i,1,n)
if (a[i].id==0)
{
int t1 = a[i].b,t2 = a[i].p;
int rest = c-t2;
if (rest<=0) continue;
int t3 = bo[0][rest][0];
if (t2<=rest && t1==t3)
t3 = bo[0][rest][1];
if (t3<=0) continue;
ans = max(ans,t1+t3);
}
//all diamonds
rep1(i,1,n)
if (a[i].id==1)
{
int t1 = a[i].b,t2 = a[i].p;
int rest = d-t2;
if (rest<=0) continue;
int t3 = bo[1][rest][0];
if (t2<=rest && t1==t3)
t3 = bo[1][rest][1];
if (t3<=0) continue;
ans = max(ans,t1+t3);
}
//half coin half diamond
rep1(i,1,n)
{
int t1 = a[i].b,t2 = a[i].p;
int rest,t3;
if (a[i].id==0)
{
rest = d;
if (t2>c) continue;
}
else
{
rest = c;
if (t2>d) continue;
}
if (rest<=0) continue;
t3 = bo[1-a[i].id][rest][0];
if (t3<=0) continue;
ans = max(ans,t1+t3);
}
cout<<ans<<endl;
return 0;
}
