== 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

Fişierul de intrare $foametea.in$ va conţine pe prima linie numerele $N$, $M$, $K$. Următoarea linie va conţine numerele $s_1_, s_2_, ..., s_n_$.

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.

h2. Date de ieşire

În fişierul de ieşire $foametea.out$ ...

Fişierul de ieşire $foametea.out$ va conţine o singură linie cu răspunsul la întrebarea $Fomistului$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 &le ... ≤ ...$

* Se garantează că se poate ajunge din oraşul $1$ în orice oraş.
h2. Exemplu