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. Mai ştim că 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. Luând în considerare 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ă, ajutaţi-l pe Fomist să afle cât de repede poate ajunge la cina festivă din oraşul N, 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?