#HDR002A. 采购

采购

题目背景

采购中心的绿票商店与黄票商店(教练在附近的时候请勿展开)

题目描述

在明日方舟两周年之际,Rosmarinus 决定到「采购中心」购买至多两个商品来庆祝。

由于一些奇怪的原因,Rosmarinus 只打算使用「资质凭证」与「高级凭证」进行购买。

在采购中心中一共有 nn 件商品,其中第 ii 件商品的价值为 viv_i,价格为 pip_i

其中,有一些商品只能通过「资质凭证」进行购买,而其他的商品只能通过「高级凭证」进行购买。

资质凭证与高级凭证不能相互转化

显然哪怕是庆祝,Rosmarinus 也是不想太亏的啦!她想向你请教,她应该如何购买商品,使得购买的商品的价值之和最大。

Rosmarinus 不可以购买两件一样的商品。假设商店中每一种商品都只有一个

输入格式

第一行输入三个正整数 n,a,bn,a,b,分别表示商店中的商品数量、Rosmarinus 拥有的「资质凭证」的数量与「高级凭证」的数量。

接下来 nn 行,每行输入两个正整数 vi,piv_i,p_i 与一个字符 cic_i,其中 viv_i 表示物品 ii 的价值,pip_i 表示物品 ii 的价格,cic_i 表示物品 ii 的种类。若 cic_iA,则表示第 ii 件物品只能通过「资质凭证」购买; 若 cic_iB,则表示第 ii 件物品只能通过「高级凭证」购买。

输出格式

一行一个正整数,表示 Rosmarinus 能过购买的物品的最大价值之和。

3 114 514
191 98 A
10 98 B
52 11 B
243

样例解释 1

购买第一件与第三件物品。

数据规模与约定

nn 有梯度。

对于 30%30\% 的数据,n10n \le 10
对于 50%50\% 的数据,n1000n \le 1000
对于 100%100\% 的数据,2n106, 0a, b, p, v1092 \le n \le 10^6,~0 \le a,~b,~p,~|v| \le 10^9