6. Oči veľké

Kubo si, ako každý iný premotivovaný prváčik na Matfyze, zapísal o trošku viac predmetov, než je bežné. Odporúčané predmety? No šak obvi. *klik* Angličtina? Veď som z nej maturoval, kredity zadarmo! *klik* Diferenciálne rovnice? Tie slová som už na gympli počul, to bude easy. *klik* Marek písal, že ide na politológiu? *klik* Čo je toto? História piva?!? To znie zaujímavo…

No ale teraz sa začal školský rok, z Kuba opadla všetká eufória a uvedomil si, že si zapísal tak približne tisíc predmetov a neexistuje ani najmenšia šanca, že by všetkými prešiel. A tak po chvíli veľmi pokojného rozmýšľania prišiel s (ako zvyčajne) geniálnym plánom. Zistí si informácie o každom predmete a vyrobí si detailný študijný plán, ktorý mu maximalizuje počet získaných kreditov!

Ale len o pár minút neskôr si o sebe uvedomil ďalšiu, ešte nepríjemnejšiu, realitu. Pred nástupom si hovoril, ako tvrdo bude pracovať, ako porazí prokrastináciu a stane sa z neho Ačkový žiak. Avšak teraz tu leží na posteli, plánu sa, samozrejme, ani nedotkol, a číta si o tom, ako sa kraby päťkrát nezávisle vyvinuli ¹. Ako sa sem dostal? Ani sám nevie. Ale jedno je jasné. Jeho práca opäť padne na vás…

Úloha

Kubo má zapísaných \(n\) predmetov. Každému predmetu prislúcha istý počet kreditov \(k_i\), ktoré Kubo získa za úspešné absolvovanie skúšky z tohto predmetu. Pre každý predmet vieme, že Kubo má ešte \(d_i\) dní do termínu skúšky a že potrebuje \(t_i\) z nich stráviť štúdiom daného predmetu, aby skúšku urobil.

Zistite, aké je najväčšie možné množstvo kreditov, ktoré vie Kubo získať.

Formát vstupu

V prvom riadku vstupu je číslo \(n\) (\(1 \leq n \leq 1\,000\)) udávajúce počet predmetov, ktoré má Kubo zapísané.

Každý z nasledujúcich \(n\) riadkov obsahuje tri čísla - \(k_i\), \(d_i\) a \(t_i\) (\(1 \leq k_i \leq 10^6, 1 \leq t_i \leq d_i \leq 20\,000\)) popisujúce jeden predmet.

Úloha má niekoľko sád vstupov, ktoré navyše spĺňajú nasledujúce obmedzenia:

Formát výstupu

Vypíš jeden riadok a v ňom jedno celé číslo - maximálny počet kreditov, ktorý dokáže Kubo získať.

Príklad

Input:

3
5 7 5
2 8 4
4 5 4

Output:

6

Prvé 4 dni strávime štúdiom tretieho predmetu a nasledujúce 4 dni štúdiom druhého. Takto spravíme skúšku z oboch z nich a tak získame 6 kreditov. Prvý predmet by nám síce dal najviac kreditov, ale okrem neho by sme nič iné nestihli a tak sa nám to neoplatí.