Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

C. Фонтаны
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Аркадий — заядлый игрок в Gardenscapes. Аркадий хочет построить два новых фонтана. Есть список из n доступных ему фонтанов, про каждый фонтан известна его красота и стоимость. В игре есть два вида денежных ресурсов: монеты и алмазы, поэтому стоимость каждого из фонтанов может быть выражена в монетах или алмазах. Монеты и алмазы нельзя обменивать друг на друга.

Помогите Аркадию выбрать два фонтана с максимальной суммарной красотой таких, что он может купить на имеющиеся у него ресурсы оба одновременно.

Входные данные

Первая строка содержит три целых числа n, c и d (2 ≤ n ≤ 100 000, 0 ≤ c, d ≤ 100 000) — количество фонтанов, количество монет и количество алмазов, которые есть у Аркадия.

В следующих n строках следует описание фонтанов. В каждой строке сначала следует два целых числа bi и pi (1 ≤ bi, pi ≤ 100 000) — красота и стоимость фонтана номер i, а затем буква «C» или «D» — в чем измеряется стоимость фонтана номер i — в монетах или в алмазах, соответственно.

Выходные данные

Выведите максимальную суммарную красоту ровно двух фонтанов, которые Аркадий может построить. Если невозможно построить два фонтана, выведите 0.

Примеры
Входные данные
3 7 6
10 8 C
4 3 C
5 6 D
Выходные данные
9
Входные данные
2 4 5
2 5 C
2 1 D
Выходные данные
0
Входные данные
3 10 10
5 5 C
5 5 C
10 11 D
Выходные данные
10
Примечание

В первом примере Аркадию нужно построить второй фонтан с красотой 4, который стоит 3 монеты. Первый фонтан он построить не сможет, так как ему не хватит на это монет. Также, Аркадию нужно построить третий фонтан с красотой 5, который стоит 6 алмазов. Таким образом, суммарная красота построенных фонтанов равна 9.

Во втором примере всего два фонтана, но Аркадий не сможет построить их оба, так как для постройки первого фонтана нужно 5 монет, а у Аркадия есть всего 4 монеты.