Simulare

simulare

== 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 <tex>N</tex> 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 <tex>S</tex> si <tex>E</tex>, <tex>S</tex> reprezentand shukarimea comentariului (frumusetea acestuia cat si valoarea sa stilistica), iar <tex>E</tex> reprezentand efortul necesar de a-l toci. Mai sunt fix <tex>M</tex> zile pana la simulare, iar Hektor isi stie programul struna. Pentru fiecare zi <tex>i</tex> din cele <tex>M</tex>, 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 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 al 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 $x ~i~$ in nodul $y ~i~$. Deoarece, anul aceste, 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 $x ~i~$ la nodul $y ~i~$ cu proprietatea ca efortul lor de invatare total este cel mult egal cu $Emax ~i~$ (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

Fişierul de intrare $simulare.in$ contine pe prima linie numerele $N$ si $M$. Pe urmatoarele $N$ linii se afla cate doua numere naturale <tex>S_i</tex> si <tex>E_i</tex> ce reprezinta shukarimea si efortul de invatare al comentariului din nodul $i$. Pe urmatoarele $N-1$ linii se afla cate doua numere naturale $x$ si $y$ cu semnificatia ca exista o muchie intre nodurile $x$ si $y$. Pe urmatoarele $M$ linii se afla cate trei numere naturale <tex>x_i</tex>, <tex>y_i</tex> si <tex>Emax_i</tex>.

Fişierul de intrare $simulare.in$ contine pe prima linie numerele $N$ si $M$. Pe urmatoarele $N$ linii se afla cate doua numere naturale $s ~i~$ si $e ~i~$ ce reprezinta shukarimea si efortul de invatare al comentariului din nodul $i$. Pe urmatoarele $N-1$ linii se afla cate doua numere naturale $x$ si $y$ cu semnificatia ca exista o muchie intre nodurile $x$ si $y$. Pe urmatoarele $M$ linii se afla cate trei numere naturale $x ~i~$, $y ~i~$ si $Emax ~i~$.

h2. Date de ieşire

În fişierul de ieşire $simulare.out$ trebuie sa se afle $M$ linii, pe linia $i$ fiind suma shukarimii maxima posibila a unei submultimi de comenatrii de pe drumul de la nodul <tex>x_i</tex> la nodul <tex>y_i</tex> cu propietatea ca suma eforturilor acestora este mai mica sau egala cu <tex>Emax_i</tex>.

În fişierul de ieşire $simulare.out$ contine $M$ linii, pe linia $i$ fiind suma shukarimii maxima posibila a unei submultimi de comenatrii de pe drumul de la nodul $x ~i~$ la nodul $y ~i~$ cu propietatea ca suma eforturilor acestora este mai mica sau egala cu $Emax ~i~$.

h2. Restricţii
* $1 ≤ N ≤ 2000$
* $1 ≤ M ≤ 20000$

* $1 &le;$ <tex>Emax_i</tex> $&le; 1000$
* $1 &le;$ <tex>s_i</tex> &le; $1.000.000$

* $1 ≤ Emax ~i~ ≤ 1000$
* $1 ≤ s ~i~ ≤ 1.000.000$

h2. Exemplu

8
|

h3. Explicaţie
 
...
 

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