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

Se da un graf orientat aciclic cu $N$ noduri si $M$ muchii si un numar natural $K$. Muchiile au costuri nenegative. Sa se determine un lant cu cel putin $K$ muchii pentru care diferenta dintre suma celor mai mari $K$ muchii de pe lant si suma celor mai mici $K$ muchii de pe lant este maxima. Nu trebuie sa gasiti lantul efectiv, ci doar sa determinati aceasta valoare.

Se da un graf orientat aciclic cu $N$ noduri si $M$ muchii si un numar natural $K$. Muchiile au costuri nenegative. Sa se determine un lant de lungime cel putin $K$ pentru care diferenta dintre suma celor mai mari $K$ elemente de pe lant si suma celor mai mici $K$ elemente de pe lant este maxima. Nu trebuie sa gasiti lantul efectiv, ci doar sa determinati aceasta valoare.

h2. Date de intrare