6. Bazošové pásy

Vedúci KSP sú hladní a nevedia sa dočkať, kedy konečne bude obed hotový. Krtko dostal extrémne dobrý nápad, že si poskladá robota, ktorý nám bude pripravovať obedy, aby to netrvalo tak dlho. Po dlhej chvíle pozerania rôznych možností na e-shopoch sa rozhodol, že najefektívnejšie bude si kúpiť továrenské pásy z Bazošu a tie zapojiť za seba. Pásy samozrejme nestačia – potrebujeme robotov, ktorý ten samotný obed budú pripravovať, kým sa vozí na páse. Zároveň sa krtkovi podarilo na matfyze vybaviť miestnosť, kde sa nám tento dlhý pás zmestí.

Úloha

Máme miestnosť, ktorá je dlhá \(l\). Na začiatku miestnosti máme kopu prázdnych tanierov na ktoré potrebujeme pripraviť obedy. Na to aby bol obed hotový, potrebuje, aby počas prípravy prešiel cez aspoň \(r\) robotov. Zároveň potrebujeme zaručiť, aby došiel presne na koniec miestnosti, kde je výdajné okienko. Na bazoši je viacero inzerátov s rôznymi pásmi – každý z nich má nejakú priepustnosť \(p\) (koľko obedov za hodinu vie tento pás previesť), dĺžku \(d\) a buď pri tomto páse je, alebo nie je robot.

Zistite, ktoré pásy má Krtko kúpiť, aby jeho výtvor vedel pripravovať obedy čo najrýchlejšie.

Formát vstupu

V prvom riadku vstupu sú 3 čísla \(n\) (\(1 \leq n \leq 1000\)), \(l\) (\(1 \leq n \leq 10^5\)), \(r\) (\(1 \leq r \leq n\)) udávajúce počet inzerátov na bazoši, dĺžku miestnosti a to koľko robotov potrebujeme na prichystanie obedu.

Potom nasleduje \(n\) riadkov – popis jednotlivých inzerátov. Pre každý inzerát máme 3 hodnoty \(d_i\), \(p_i\) (\(1 \leq p_i \leq 10^6\)), \(r_i\). \(d_i\) je dĺžka pásu na tomto inzeráte, \(p_i\) je jeho priepustnosť a \(r_i\) je A ak tento pás obsahuje robota a N ak nie.

Navyše v 3. sade je \(r = 0\), teda netreba žiadnych robotov.

Formát výstupu

Na výstup vypíš jedno číslo - najväčšiu priepustnosť, ktorú vie mať pás dlhý presne \(l\) a s aspoň \(r\) robotmi.

Ak pás zostrojiť nevieme, tak vypíš -1.

Príklady

Input:

4 100 0
40 1500 N
60 700 A
25 850 N
35 2700 A

Output:

850

Najviac sa oplatí kúpiť prvý, tretí a štvrtý pás. Mohli by sme aj prvý a druhý, ale potom by sme mali menšiu priepustnosť

Input:

3 200 2
100 1700 N
100 1500 A
100 1300 A

Output:

1300

Musíme použiť všetky pásy s robotmi, inak nevieme pripraviť obed

Input:

1 100 0
110 4747 A

Output:

-1

Jediný inzerát, čo máme nám ponúka až príliš dlhý pás - nezmestí sa nám do miestnosti