4. Školské pomôcky

Škola sa zas nezastaviteľne blíži a Peťko si musí ísť kúpiť nové pomôcky. Po dlhom prieskume obchodov sa rozhodol ísť do KSP¹, kde majú najkvalitnejšie školské pomôcky. Možno sa pýtate, prečo Peťkovi tak veľmi záležalo na ich kvalite? On sa totiž toto leto dočítal v časopise, že čím lepšiu súpravu pomôcok bude mať, tým viac sa mu bude dariť v škole. A to sa oplatí.

Nie je to však také jednoduché, pretože celková kvalita súpravy školských pomôcok je taká kvalitná, ako jej najmenej kvalitná pomôcka. Taktiež, Peťko nemá neobmedzene veľa peňazí a celková cena sa musí zmestiť do vreckového od jeho rodičov. Celý tento proces je náročnejší ako si Peťko myslel a teraz má hlavu v smútku, pretože sa mu nechce rozmýšlať², ktoré pomôcky si má vybrať. Pomôžte mu s jeho dilemou, aby sa mu tento rok čo najviac darilo.

Úloha

V obchode majú rôzne typy školských pomôcok – pero, ceruzka, zošit… označené číslami od \(1\) po \(t\). Každá pomôcka má tri atribúty – typ, cena, kvalita. Peťko chce nakúpiť pomôcky tak,

1. aby mal z každého typu jednu;
2. aby cena jeho nákupu nepresiahla peniaze, ktoré má k dispozícií;
3. a aby celková kvalita súpravy pomôcok bola čo najväčšia.

Peťko má na výber z \(n\) pomôcok a má k dispozícií \(m\) peňazí. Celková kvalita nákupu sa rovná kvalite najmenej kvalitnej pomôcky. Zistite celkovú kvalitu Peťkovho nákupu.

Formát vstupu

Na prvom riadku dostanete tri čísla \(t\) (počet typov školských pomôcok), \(n\) (počet pomôcok na výber) a \(m\) (vreckové od rodičov). Na ďalších \(n\) riadkoch dostanete tri čísla – \(t\) udávajúce typ pomôcky, \(c\) (\(0 \leq c \leq 2 \cdot m\)) udávajúce cenu pomôcky a \(k\) (\(1 \leq k \leq 5 \cdot n\)) udávajúce kvalitu pomôcky.

V jednotlivých sadách platia nasledujúce obmedzenia:

Formát výstupu

Vypíšte jeden riadok a v ňom jedno celé číslo udávajúce celkovú kvalitu súpravy kúpených pomôcok. Ak sa pomôcky nedajú kúpiť, vypíšte \(0\).

Príklady

Input:

2 6 20
1 16 24
1 8 11
2 12 18
1 6 7
2 13 15
2 25 15

Output:

11

Peťko chce maximalizovať kvalitu jeho pomôcok, lenže najkvalitnejšie stoja \(16 + 12 = 28\), čo je viac ako \(20\). Preto si nekúpi najkvalitnejšiu pomôcku typu \(1\), ale druhú najkvalitnejšiu. Jeho nákup bude stáť \(8 + 12 = 20\). Celková kvalita súpravy pomôcok je \(11\), pretože pomôcka s najmenšou kvalitou má kvalitu \(11\).

Input:

2 6 12
2 8 17
1 6 10
1 9 4
2 12 5
2 11 23
1 12 5

Output:

0

Ak si chce Peťko kúpiť z každého typu predmetu jeden, tak mu na to nevýjdu peniaze.