← 返回题目列表

Codeforces · 799/C

C. 喷泉

中文机器翻译题面 查看原题

阿尔卡迪经常玩《花园风景》。阿尔卡迪想要建造两个新喷泉。有 n 个可用的喷泉,每个喷泉的美丽和成本都是已知的。游戏中有两种类型的金钱:金币和钻石,因此每个喷泉的成本可以是金币或钻石。不同类型之间不允许进行货币兑换。

帮助阿尔卡迪找到两个最美丽的喷泉,以便他可以同时购买两个。

输入

第一行包含三个整数 n、c 和 d (2 ≤ n ≤ 100 000, 0 ≤ c, d ≤ 100 000) — 喷泉的数量、Arkady 拥有的硬币和钻石的数量。

接下来的 n 行描述喷泉。每行包含两个整数 bi 和 pi (1 ≤ bi, pi ≤ 100 000)——第 i 个喷泉的美丽和成本,然后是字母“C”或“D”,描述第 i 个喷泉的成本是哪种类型的货币:分别是硬币或钻石。

输出

打印阿尔卡迪可以建造的两个喷泉的最大总美感。如果他不能建造两个喷泉,则打印 0。

示例

输入 #1

3 7 6
10 8 C
4 3 C
5 6 D

输出 #1

9

输入 #2

2 4 5
2 5 C
2 1 D

输出 #2

0

输入 #3

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

输出 #3

10

注意

在第一个例子中,Arkady 应该建造第二个美丽程度为 4 的喷泉,花费 3 个硬币。他无法建造第一个喷泉,因为他没有足够的硬币。另外,阿尔卡迪应该建造第三个喷泉,美丽5,花费6钻石。因此已建成喷泉的总美度为 9。

在第二个例子中,有两个喷泉,但阿尔卡迪无法建造两个喷泉,因为他需要 5 个硬币来建造第一个喷泉,而阿尔卡迪只有 4 个硬币。