== 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. 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^2^ + 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$.

$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^2^ + 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$.

h2. Date de intrare