== 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 pe care le cară în traistă pe acel drum. 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. 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$**.

h2. Date de intrare

* $1 ≤ N ≤ 5000$
* $1 ≤ M ≤ 25000$
* $0 ≤ K ≤ 30$

* $0 ≤ s{~i~} ≤ K$

* $1 ≤ A, B ≤ N$
* $0 ≤ L ≤ 10000$
* $0 ≤ C ≤ K$

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. În oraşul 3 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^) momente de timp. Răspunsul final este, aşadar 43.
2. $Fomistul$ nu poate ajunge în oraşul $5$.

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