$Fomistul$ locuieşte într-o ţară cu $N$ oraşe conectate prin $M$ drumuri unidirecţionale. $Fomistul$ este pasionat de mersul viguros, dar acesta nu poate face niciun pas fără să fi mâncat o cantitate rezonabilă de sarmale în avans. În fiecare dintre cele $N$ oraşe, acesta cunoaşte o mătuşă care îi poate oferi maxim $s{~i~}$ sarmale la fiecare vizita a sa în oraşul respectiv. $Fomistul$, nefiind adeptul expresiei populare "sac fără fund", poate depozita maxim $K$ sarmale în stomacul său. Unele drumuri sunt mai greu de parcurs decât altele, fiecare costându-l pe $Fomist$ un număr de sarmale. Un detaliu important este că Fomistul se mişcă cu atât mai greu cu cât a mâncat mai multe sarmale. În consecinţă, dacă a mâncat suficient pentru a parcurge un drum de lungime $L$, atunci îl va parcurge în $L * (S^2^ + 1)$ unităţi de timp, unde $S$ este numărul de sarmale pe care le are în stomac în momentul începerii deplasării viguroase pe drumul respectiv. Ajutaţi-l pe Fomist să afle cât de repede poate ajunge la cina festivă din oraşul $N$, ştiind că pleacă din oraşul 1.

$Fomistul$ nostru preferat locuieşte într-o ţară cu $N$ oraşe conectate prin $M$ drumuri unidirecţionale. Fiecare drum din ţara sa are o anumită lungime, *L{~i~}** şi o anumită dificultate **C{~i~}**, marcată de numărul de sarmale pe care $Fomistul$ trebuie să le consume **în avans** pentru a îl putea parcurge cu succes. Mai ştim că acesta poate purta cu sine maxim **$K$** sarmale, dar din fericire, în fiecare oraş cunoaşte câte o mătuşă care îi oferă maxim **s{~i~}** sarmale (în limita valorii $K$) la fiecare vizită pe care i-o face.

$Fomistul$ nostru preferat locuieşte într-o ţară cu $N$ oraşe conectate prin $M$ drumuri unidirecţionale. Fiecare drum din ţara sa are o anumită lungime, **L{~i~}** şi o anumită dificultate **C{~i~}**, marcată de numărul de sarmale pe care $Fomistul$ trebuie să le consume **în avans** pentru a îl putea parcurge cu succes. Mai ştim că acesta poate purta cu sine maxim **$K$** sarmale, dar din fericire, în fiecare oraş cunoaşte câte o mătuşă care îi oferă maxim **s{~i~}** sarmale (în limita valorii $K$) la fiecare vizită pe care i-o face.

h2. Date de intrare