Fişierul intrare/ieşire:simulare.in, simulare.outSursăConcursul National de Informatica "Adolescent Grigore Moisil" 17
AutorChichirim GeorgeAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test0.6 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Simulare

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 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 programul 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 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 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).

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 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.

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 x_i la nodul y_i cu propietatea ca suma eforturilor acestora este mai mica sau egala cu Emax_i.

Restricţii

  • 1 ≤ N ≤ 2000
  • 1 ≤ M ≤ 20000
  • 1 ≤ Emax_i ≤ 1000
  • 1 ≤ s_i1.000.000

Exemplu

simulare.insimulare.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?