== 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^ + L)$ 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

Fişierul de intrare $foametea.in$ va conţine pe prima linie numerele $N$ (numărul de oraşe), $M$ (numărul de drumuri), $K$ (capacitatea stomacului $Fomistului$). Următoarea linie va conţine numerele $s{~1~}, s{~2~}, ..., s{~N~}$ (numărul maxim de sarmale oferit de mătuşă în fiecare dintre cele $N$ oraşe). Următoarele $M$ linii vor conţine fiecare câte 4 întregi, $A$, $B$, $C$, $D$ semnificând că există un drum ce pleacă din oraşul $A$, ajunge în oraşul $B$, are lungimea $C$ şi poate fi parcurs de $Fomist$ dacă consumă $D$ sarmale.

Fişierul de intrare $foametea.in$ va conţine pe prima linie numerele $N$ (numărul de oraşe), $M$ (numărul de drumuri), $K$ (capacitatea stomacului $Fomistului$). Următoarea linie va conţine numerele $s{~1~}, s{~2~}, ..., s{~N~}$ (numărul maxim de sarmale oferit de mătuşă în fiecare dintre cele $N$ oraşe). Următoarele $M$ linii vor conţine fiecare câte 4 întregi, $A$, $B$, $L$, $S$ semnificând că există un drum ce pleacă din oraşul $A$, ajunge în oraşul $B$, are lungimea $C$ şi poate fi parcurs de $Fomist$ dacă consumă $D$ sarmale.

h2. Date de ieşire