== 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 în traistă maxim **$K$** sarmale şi, din fericire, în fiecare oraş cunoaşte câte o mătuşă care îi oferă maxim **s{~i~}** sarmale la fiecare vizită a sa în oraşul cu pricina. 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, pentru că îi este prea foame pentru a se descurca singur, vă roagă să îi spuneţi 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, din fericire, în fiecare oraş cunoaşte câte o mătuşă care îi oferă maxim **s{~i~}** sarmale la fiecare vizită a sa în oraşul cu pricina. 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 care îi rămân în traistă după ce consumă cantitatea necesară parcurgerii drumului respectiv. Fomistul, pentru că îi este prea foame pentru a se descurca singur, vă roagă să îi spuneţi 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 traistei $Fomistului$).
Următoarea linie va conţine numerele $s{~1~}, s{~2~}, ..., s{~N~}$ (numărul maxim de sarmale oferit de mătuşa din fiecare dintre cele $N$ oraşe).

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 fiecare dintre cele $N$ mătuşi).

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.
h2. Date de ieşire
Fişierul de ieşire $foametea.out$ va conţine o singură linie cu răspunsul la întrebarea $Fomistului$.

În cazul în care acesta nu poate ajunge la cina festivă afişaţi mesajul "Fomistul moare de foame" (fără ghilimele).

**În cazul în care acesta nu poate ajunge la cina festivă afişaţi mesajul "Fomistul moare de foame" (fără ghilimele).**

h2. Restricţii
* $1 ≤ N ≤ 5000$
* $1 ≤ M ≤ 25000$
* $0 ≤ K ≤ 30$

* $0 ≤ s{~i~} ≤ K$

* $1 ≤ A, B ≤ N$
* $0 ≤ L ≤ 10000$
* $0 ≤ C ≤ K$

h2. Precizări
* Pentru teste în valoare de 20 puncte se garantează că $L$ = 1 şi că $C$ = 0 pentru toate drumurile.

* Pentru teste în valoare de 20 puncte se garantează că $C$ = 0 pentru toate drumurile şi că nu există cicluri (graful rezultat este un DAG).
* Pentru teste în valoare de 30 de puncte se garantează că $C$ = 0 pentru toate drumurile.
* În fiecare oraş $Fomistul$ poate alege să mănânce oricâte sarmale între 0 şi s{~i~} cu condiţia să nu depăşască limita de $K$.
* $Fomistul$ are iniţial $0$ sarmale în traistă. Va lua cât consideră de cuviinţă de la mătuşa din primul oraş.

* Pentru alte teste în valoare de 20 puncte se garantează că $C$ = 0 pentru toate drumurile şi că nu există cicluri (graful rezultat este un DAG).
* Pentru alte teste în valoare de 30 de puncte se garantează că $C$ = 0 pentru toate drumurile.
* Pentru alte teste în valoare de 30 de puncte se aplică restricţiile iniţiale.
* **În fiecare oraş i, Fomistul poate alege să introducă în traistă oricâte sarmale între 0 şi s{~i~}, cu condiţia ca numărul total să nu depăşască limita de $K$.**
* **Fomistul are iniţial $0$ sarmale în traistă. Va lua cât consideră de cuviinţă de la mătuşa din primul oraş.**

h2. Exemplu

5 4 0 2
3 5 8 2
1 3 7 2

| 159

| 43

|
| 5 3 5
2 3 1 0 1

3 2 3 23
3 4 4 20
6 1 3 14

|3374

|327

|
h3. Explicaţie

1. $Fomistul$ mănâncă 4 sarmale în primul oraş, ajunge în oraşul $3$ în 7 * (1 + 4^2^) = 119, iar apoi în oraşul $5$ în 119 + 8 * (1 + 2^2^) = 159.
2. $Fomistul$ nu poate ajunge în oraşul $5$.

ex. 1:
Fomistul îşi încarcă în traistă 4 sarmale din primul oraş.
Se pregăteşte de drumul (1, 3) mâncând 2 dintre sarmalele din traistă şi ajunge în oraşul 3 în $7 * (1 + 2^2^) = 35$ unităţi de timp.
În oraşul 3 nu i se oferă nicio sarma.
Se pregăteşte de drumul (3, 5) mâncând 2 sarmale şi ajunge în oraşul 5 după încă $8 * (1 + 0^2^) = 8$ momente de timp.
Răspunsul final este, aşadar $35 + 8 = 43$.
 
ex. 2:
Fomistul nu poate ajunge în oraşul 5.

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