阿尔卡迪经常玩《花园风景》。阿尔卡迪想要建造两个新喷泉。有 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 个硬币。