题目描述

考古学家小z在探索古墓时发现了 $N$ 颗珍贵的宝石。每颗宝石都有以下属性：

• 重量 $w_i$（携带时消耗的体力）
• 价值 $v_i$（考古研究价值）
• 颜色 $c_i$（红色'R'或蓝色'B'）

小z的探险背包有以下限制：

1. 最多只能承受 $V$ 点重量的宝石
2. 红色宝石最多携带 $R$ 颗
3. 蓝色宝石最多携带 $B$ 颗

请帮助小z选择要带走的宝石，在满足所有限制条件的情况下，使得带走的宝石总研究价值最大。

输入格式

第一行四个整数 $N,V,R,B$
接下来 $N$ 行，每行两个整数 $w_i,v_i$ 和一个字符 $c_i$

输出格式

输出一个整数表示最大总价值

样例

输入样例

4 10 2 1
2 5 R
3 8 B
4 6 R
5 7 B

输出样例

19

数据范围

$1 \leq N \leq 100$

$1 \leq V \leq 500$

$0 \leq R,B \leq 50$

$1 \leq w_i,v_i \leq 100$