Zadanie

GreedIsGood

Počet bodov: 40

V dávnych, dobrých časoch, bola Warcraft 3 populárna hra. Gurmánom počítačových hier medzi vami možno niečo hovorí hláška GreedIsGood. Tento cheatcode hráčovi pridá ľubovoľné množstvo zlata a dreva, čo sú zdroje potrebné na všetko, od najatia jednotiek po stavanie budov.

Nemenovaný hráč známy vo svete Warcraftu len ako ‘fezjo’ by však takto nikdy nepodvádzal.

V tomto momente má presne \(e\) zlata a \(p\) dreva¹. Má na výber spomedzi \(n\) rôznych, unikátnych hrdinov, ktorých môže pridať do svojej armády - chce si najať presne dvoch. Každý má nejakú bojovú silu, a nejakú cenu (buď v dreve, alebo v zlate).

Pomôžete mu zistiť, aký najväčší súčet bojovej sily vie pridať svojej armáde!

Vstup a výstup

V prvom riadku vstupu sú tri celé čísla \(n\), \(e\) a \(p\): počet hrdinov a fezjove zásoby zlata a dreva.

Nasledujúcich \(n\) riadkov popisuje jedného hrdinu tokenmi \(s_i\ c_i\ z_i\). \(s_i\) je sila daného hrdinu, \(c_i\) je jeho cena a \(z_i\) je zdroj - E alebo P - v ktorom je hrdinova cena.

Platí \(2 \leq n \leq 200\,000\) a \(1 \leq s_i,c_i,e,p \leq 10^9\). V polovici vstupov \(n \leq 1000\).

Každého uvedeného hrdinu si môže fejzo najať iba raz. Ak si fezjo nemôže najať žiadnych dvoch hrdinov, vypíšte v jednom riadku Reality is often disappointing.

Inak vypíšte najväčší súčet síl dvoch hrdinov, ktorých si fezjo vie oboch naraz zakúpiť a nepresiahnuť pritom svoj rozpočet zlata a dreva.

Príklad

Input:

4 10 20
5 3 E
6 8 P
8 10 P
9 13 P

Output:

14

Najlepšie, čo fezjo vie spraviť, je zakúpiť si druhého a tretieho hrdinu. Bude ho to stáť 8+10 = 18 dreva, čo je pod jeho rozpočet 20, a súčet ich síl je 8+6=14

Input:

2 10 10
6 6 E
6 6 E

Output:

Reality is often disappointing

Aby si zakúpil oboch hrdinov, potreboval by fezjo 12 zlata. Má ho však len 10.

Input:

2 10 10
6 6 E
6 6 P

Output:

12