== 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).
Poveste şi cerinţă...
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$ ...
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$ ...
h2. Restricţii
* $1 ≤ N ≤ 2000$
* $1 ≤ M ≤ 20000$
* $1 ≤$ <tex>Emax_i</tex> $≤ 1000$
* $1 ≤$ <tex>s_i</tex> ≤ $1.000.000$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. simulare.in |_. simulare.out |
| 10 6
5 5
3 9
4 4
10 1
3 1
8 10
1 5
1 1
1 9
5 7
10 7
9 7
5 9
3 10
4 5
8 10
1 5
6 1
2 1
8 7 10
1 5 14
1 4 12
1 1 18
6 9 20
6 1 14
| 6
8
18
5
16
8
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="simulare") ==
