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

Se da un arbore cu $N$ noduri si $M$ paznici. Pentru a angaja paznicul $i$ trebuie sa platesti costul $Z{~i~}$. Se stie ca daca angajezi paznicul $i$, atunci acesta va pazi toate nodurile de pe lantul de la nodul $A{~i~}$ pana la nodul $B{~i~}$. Se cere sa se determine costul minim pentru a pazi tot arborele. Un nod nu are voie sa fie pazit de mai mult de un paznic.

Se da un arbore cu $N$ noduri si $M$ paznici. Pentru a angaja paznicul $i$ trebuie sa platesti costul $Z{~i~}$. Se stie ca daca angajezi paznicul $i$, atunci acesta va pazi tot lantul din arbore de la nodul $A{~i~}$ pana la nodul $B{~i~}$. Se cere sa se determine costul minim pentru a pazi tot arborele. Un nod nu are voie sa fie pazit de mai mult de un paznic.

h2. Date de intrare