Š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[^1], 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ť[^2], 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.