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 [^1]. 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í.