Foametea

foametea

== 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 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$**.

$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$ (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.

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

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).**

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

* $0 ≤ C ≤ 10000$
* $0 ≤ D ≤ K$

h2. Precizări

* Pentru teste în valoare de 20 puncte se garantează că $L$ = 1 şi că $C$ = 0 pentru toate drumurile.
* 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ş.**

* Pentru teste în valoare de 15 puncte se garantează că $C$ = 1 şi că $D$ = 0 pentru toate drumurile.
* Pentru teste în valoare de 15 puncte se garantează că $D$ = 0 pentru toate drumurile şi că nu există cicluri (graful rezultat este un DAG).
* Pentru teste în valoare de 20 de puncte se garantează că $D$ = 0 pentru toate drumurile.
* Se garantează că se poate ajunge din oraşul $1$ în orice oraş.
* În fiecare oraş $Fomistul$ poate alege să mănânce oricâte sarmale între 0 şi s{~i~} dacă nu depăşeşte limita de $K$.
* $Fomistul$ are iniţial $0$ sarmale în stomac. Va mânca cât consideră că se cuvine din oraşul $1$.

h2. Exemplu
table(example). |_. foametea.in |_. foametea.out |

| 5 3 5
4 3 0 2 0
5 4 0 2
3 5 8 2
1 3 7 2
| 43
|
| 5 3 5
2 3 1 0 1
2 1 5 4
1 5 2 4
1 4 5 4
| Fomistul moare de foame
|
|6 10 24
24 11 15 8 16 23
2 6 2 19
1 3 5 0
5 4 3 12
2 5 4 12
4 2 5 9
3 5 3 21
1 2 5 15
3 2 3 23
3 4 4 20
6 1 3 14
|327
|

| 5 5 5
 3 2 2 0 3
 5 2 2 4
 3 2 8 1
 5 3 4 3
 4 5 9 0
 1 5 4 1
| 8
|

h3. Explicaţie

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