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

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

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 ≤ C ≤ 10000
• 0 ≤ D ≤ K

Precizări

• 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.
• Î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. 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?