Problem C
Heimanámsálag

Mynd fengin af publicdomainpictures.net

Fyrir einhverjum árum síðan lét Rektor Menntaskólans á Akureyri alræmd orð falla. Hann hélt því fram að ef nemendur væri einfaldlega niður í skóla klukkutíma eftir kennslu á hverjum degi þá væri ekkert heimanám eftir þegar þau færu heim og að kvartanir um heimanámsálag væru því ekki neitt til að hlusta á.

Nemendur sem hafa verið í, eða eru í, Menntaskólanum á Akureyri (eða flest öðrum framhaldsskólum landsins) vita að þetta er tóm þvæla. Allir sem hafa þurft láta sig hafa Íslandsáfanga Menntaskólans á Akureyri þekkja það sérstaklega vel. Til að sýna hversu mikil þvæla þetta er þá er búið að safna gögnum um allt heimanám sem er sett fyrir og ætlum við að rannsaka hversu mikið þarf að vinna á dag til að klára allt saman.

Íslendingasögur, atómskáld, læra nöfnin á fossum og hvalategundum Íslands, og eins gott að þú leggir á minnið uppáhaldssundlaug kennarans til að ná bónusspurningunni! Hrein vitleysa, ég gæti haldið áfram í allan dag! Það ætti að leggja þetta niður með einu og öllu-

Ha? Nei ég er að skrifa dæmalýsinguna ennþá. Hei! Nei- ég er ekki búinn! Láttu lyklaborðið í frið-

Afsakið þetta.

Hvert verkefni er sett fyrir á einhverjum degi og þarf að ljúka í síðasta lagi á einhverjum degi. Þar að auki tekur hvert verkefni einhvern tiltekinn fjölda tímaeininga að klára. Ef þú ætlar alltaf að vinna $x$ tímaeiningar á dag (nema þú sért búin/n með allt heimanám), hvað þarf $x$ að vera stórt í minnsta lagi til að klára öll verkefni á ásettum tíma?

Inntak

Fyrsta lína inntaksins inniheldur eina heiltölu $n$, fjölda verkefna. Ávallt gildir $0 \leq n \leq 100\, 000$. Næst fylgja $n$ línur þar sem $i$-ta þeirra lýsir $i$-ta verkefninu.

Hver slík lína inniheldur þrjár heiltölur $a_i, b_i, t_i$ þar sem $a_i$ er á hvaða degi það er sett fyrir, $b_i$ er á hvaða degi á að skila, og $t_i$ er hvað verkefnið tekur margar tímaeiningar. Athugið að hægt er að vinna í verkefni og skila því í lok dags. Ávallt gildir að $0 \leq a_i, b_i, t_i \leq 10^9$ og $a_i \leq b_i$.

Athugið að tölurnar í dæminu eru stórar og útreikningar passa mögulega ekki í $32$ bita.

Úttak

Prentaðu hvað þú þarft að vinna margar tímaeiningar á dag til að klára öll verkefni á ásettum tíma.

Stigagjöf

3
1 4 3
2 3 4
4 4 1

2

3
1 10 20
4 4 5
4 4 0

5