== include(page="template/taskheader" task_id="foametea") ==

$Fomistul$ nostru preferat 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$ 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 are o lungimea $l~i~$

h2. Date de intrare