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

Poveste şi cerinţă...

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

Fişierul de intrare $kgraf.in$ ...

Fişierul de intrare $kgraf.in$ contine pe prima linie numerele $N,M$ si $K$. Pe ficare dintre urmatoarele $M$ linii se va gasi cate un triplet de forma $a,b,c$, cu proprietatea ca exista muchie de la $a$ la $b$ de cost $c$.

h2. Date de ieşire

În fişierul de ieşire $kgraf.out$ ...

În fişierul de ieşire $kgraf.out$ se va scrie un singur numar $S$ reprezentand valoarea ceruta in enunt.

h2. Restricţii

h2. Exemplu
table(example). |_. kgraf.in |_. kgraf.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 3 4 2
1 3 0
2 1 0
1 3 4
2 1 4
| 0

|
h3. Explicaţie