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 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, nefiind adeptul expresiei populare "sac fără fund", 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. Un detaliu important este că Fomistul se mişcă cu atât mai greu cu cât a mâncat mai multe sarmale. În consecinţă, dacă a mâncat suficient pentru a parcurge un drum de lungime L, atunci îl va parcurge în L * (S² + 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.

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, marcată de numărul de sarmale pe care Fomistul trebuie să le consume în avans pentru a îl putea parcurge cu succes. Mai ştim că acesta poate purta cu sine maxim K sarmale, dar 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. 

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?