== 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. Fiecare drum din ţara sa are o anumită lungime, **L{~i~}** şi o anumită dificultate **C{~i~}**, egală cu numărul de sarmale pe care $Fomistul$ trebuie să le consume **la începerea** deplasării pe respectivul drum pentru a-l putea parcurge cu succes. Acesta poate căra cu sine maxim **$K$** sarmale şi că, 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. Este bine cunoscut faptul că timpul necesar parcurgerii unui drum de lungime $l$ este egal cu $l * (s^2^ + 1)$, unde $s$ este numărul de sarmale pe care le cară în momentul respectiv. $Fomistul$ vă roagă să afle cât de repede poate ajunge la cina festivă din oraşul $N$ (unde se vor servi sarmale), plecând 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~}**, egală cu numărul de sarmale pe care $Fomistul$ trebuie să le consume **la începerea** deplasării pe respectivul drum pentru a-l putea parcurge cu succes. Acesta poate căra în traistă maxim **$K$** sarmale şi că, 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. Este bine cunoscut faptul că timpul necesar parcurgerii unui drum de lungime $l$ este egal cu $l * (s^2^ + 1)$, unde $s$ este numărul de sarmale pe care le cară în momentul respectiv în traistă. $Fomistul$ vă roagă să afle cât de repede poate ajunge la cina festivă din oraşul $N$ (unde se vor servi sarmale), plecând 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$).

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 traistei $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$, $C$ semnificând că există un drum ce pleacă din oraşul $A$, ajunge în oraşul $B$, are lungimea $L$ şi poate fi parcurs de $Fomist$ consumând $C$ sarmale din rezerva sa.