== include(page="template/taskheader" task_id="simulare") ==

Deoarece anul trecut nu ati reusit sa-l ajutati pe 'Hektor':http://www.infoarena.ro/problema/hektor sa treaca bacul, el este nevoit sa-l dea si anul acesta. Vreme trece, vreme vine si s-au apropiat simularile. Anul trecut, Hektor nu a invatat pentru simularea la romana pentru ca a zis atunci ca mult mai este pana la bac si ca are timp destul sa invete (evident, acesta s-a inselat). Tara in care locuieste Hektor are forma unui arbore cu $N$ noduri. Deoarece acesta este un interlop cu relatii internationale, el cunoaste cate o profesoara de romana in fiecare nod al tarii care ii poate da cate un comentariu de invatat pentru simulare. Fiecare comentariu este caracterizat de doua numere $S$ si $E$, $S$ reprezentand shukarimea comentariului (frumusetea acestuia cat si valoarea sa stilistica), iar $E$ reprezentand efortul necesar de a-l toci. Mai sunt fix $M$ zile pana la simulare, iar Hektor isi stie progrmul struna. Pentru fiecare zi $i$ din cele $M$, el are niste afaceri de indeplinit, astfel acesta fiind nevoit sa se deplaseze din nodul <tex>x_i</tex> in nodul <tex>y_i</tex>. Deoarece, anul acesta, Hektor este pus pe invatat, ci nu numai pe afaceri murdare, el ar vrea sa stie care e shukarimea maxima totala pe care ar putea sa o obtina daca el ar putea lua niste comentarii de pe drumul de la nodul <tex>x_i</tex> la nodul <tex>y_i</tex> cu proprietatea ca efortul lor de invatare total este cel mult egal cu <tex>Emax_i</tex> (el isi devota putin timp pentru a invata, dar totusi are si niste afaceri mult mai importante de rezolvat si nu isi permite sa se oboseasca prea tare cu invatatul).

Deoarece anul trecut nu ati reusit sa-l ajutati pe 'Hektor':http://www.infoarena.ro/problema/hektor sa treaca bacul, el este nevoit sa-l dea si anul acesta. Vreme trece, vreme vine si s-au apropiat simularile. Anul trecut, Hektor nu a invatat pentru simularea la romana pentru ca a zis atunci ca mult mai este pana la bac si ca are timp destul sa invete (evident, acesta s-a inselat). Tara in care locuieste Hektor are forma unui arbore cu $N$ noduri. Deoarece acesta este un interlop cu relatii internationale, el cunoaste cate o profesoara de romana in fiecare nod al tarii care ii poate da cate un comentariu de invatat pentru simulare. Fiecare comentariu este caracterizat de douna numere $S$ si $E$, $S$ reprezentand shukarimea comentariului (frumusetea acestuia cat si valoarea sa stilistica), iar $E$ reprezentand efortul necesar de a-l toci. Mai sunt fix $M$ zile pana la simulare, iar Hektor isi stie progrmul struna. Pentru fiecare zi $i$ din cele $M$, el are niste afaceri de indeplinit, astfel acesta fiind nevoit sa se deplaseze din nodul <tex>x_i</tex> in nodul <tex>y_i</tex>. Deoarece, anul acesta, Hektor este pus pe invatat, ci nu numai pe afaceri murdare, el ar vrea sa stie care e shukarimea maxima totala pe care ar putea sa o obtina daca el ar putea lua niste comentarii de pe drumul de la nodul <tex>x_i</tex> la nodul <tex>y_i</tex> cu proprietatea ca efortul lor de invatare total este cel mult egal cu <tex>Emax_i</tex> (el isi devota putin timp pentru a invata, dar totusi are si niste afaceri mult mai importante de rezolvat si nu isi permite sa se oboseasca prea tare cu invatatul).

h2. Date de intrare