== 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$ nostru nu e spart, aşa că 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. Tineţi cont şi ca Fomistul se mişcă cu atât mai greu cu cât a mâncat mai multe sarmale (că na, atârnă). Î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. $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$ nostru nu e spart, aşa că 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. Tineţi cont şi ca Fomistul se mişcă cu atât mai greu cu cât a mâncat mai multe sarmale (că na, atârnă). Î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.

h2. Date de intrare