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 progrmul 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':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).

h2. Date de intrare