Fişierul intrare/ieşire:	foametea.in, foametea.out	Sursă	FMI No Stress 9
Autor	Stefan Radu	Adăugată de	FMI No Stress 9 •fminostress9
Timp execuţie pe test	0.2 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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² + 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.

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₁, s₂, ..., 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. 

Date de ieşire

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

Restricţii

• 1 ≤ N ≤ 5000
• 1 ≤ M ≤ 25000
• 0 ≤ K ≤ 30
• 1 ≤ A, B ≤ N
• 0 ≤ L ≤ 10000
• 0 ≤ C ≤ K

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 stomac. Cât consideră că se cuvine din oraşul 1, atâta va şi consuma.

Exemplu

Explicaţie

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

Cum se trimit solutii?