== include(page="template/taskheader" task_id="curcani") ==
Aflând de intenţiile lui Rick de a se transforma într-un curcan de Ziua Recunosţintei pentru a nu mai fi marcat drept terorist, preşedintele Curtis se hotărăşte să trimită o armată de curcani pe urmele lui. Reşedinţa preşedintelui se află în oraşul cu numărul $1$, iar Rick se află în oraşul $N$. Oraşele sunt conectate între ele prin $M$ străzi unidirecţionale de diferite lungimi. Curcanii se află iniţial în nodul $1$ şi vor să ajungă la Rick, adică în nodul $N$, pe cel mai scurt drum.

Rick are posibilitatea să mărească lungimile muchiilor pentru a încetini armata de curcani, dar cu un anumit cost. Mai exact, costul pentru a mări muchia $i$ cu $j$ unităţi este $A[i][j]$. Pentru a căştiga timp, Rick vrea să mărească muchiile grafului astfel încât *lungimea celui mai scurt drum intre $1$ şi $N$ să fie cu $K$ unităţi mai mare decât era iniţial*. În plus, ştim că $A[i][j-1] - A[i][j-2] <= A[i][j] - A[i][j-1].$

Rick are posibilitatea să mărească lungimile muchiilor pentru a încetini armata de curcani, dar cu un anumit cost. Mai exact, costul pentru a mări muchia $i$ cu $j$ unităţi este $A[i][j]$. Pentru a căştiga timp, Rick vrea să mărească muchiile grafului astfel încât lungimea tuturor drumurilor intre $1$ şi $N$ să fie cu $K$ unităţi mai mare decât era iniţial. În plus, ştim că $A[i][j-1] - A[i][j-2] <= A[i][j] - A[i][j-1].$

Ajutaţi-l pe Rick să afle *costul minim* pentru ca lungimea drumului minim dintre $1$ şi $N$ să fie cu $K$ unităţi mai mare decât era iniţial.

Ajutaţi-l pe Rick să afle *costul minim* pentru ca lungimea drumului minim dintre $1$ şi $N$ să fie cu cel putin $K$ unităţi mai mare decât era iniţial.

h2. Date de intrare

* $1 ≤ K ≤ 5$
* $1 ≤ N ≤ 250$
* $1 ≤ M ≤ 1000$ ??

* Se garantează că graful este conex şi aciclic

* Se garantează că graful aciclic si exista cel putin un drum de la $1$ la $N$.

h2. Subtaskuri

* *$Subtaskul 1 (10 de puncte):$* $N ≤ 8$, $K ≤ 2$  ,$M ≤ 12$
* *$Subtaskul 2 (20 de puncte):$* Graful este format din mai multe lanţuri independente de la 1 la N
* *$Subtaskul 3 (20 de puncte):$* Nodurile de la $1$ la $N-1$ formează un arbore, iar toate frunzele acestuia sunt conectate de nodul $N$
* *$Subtaskul 4 (20 de puncte):$* $K = 1$
* *$Subtaskul 5 (30 de puncte):$* restricţiile iniţiale

* *$Subtaskul 1 (10 de puncte):$* $N ≤ 8$, $K ≤ 2$ ,$M ≤ 12$
* *$Subtaskul 2 (20 de puncte):$* Graful este format din mai multe lanţuri independente de la $1$ la $N$.
* *$Subtaskul 3 (20 de puncte):$* Nodurile de la $1$ la $N-1$ formează un arbore, iar toate frunzele acestuia sunt conectate de nodul $N$.
* *$Subtaskul 4 (20 de puncte):$* $K = 1$.
* *$Subtaskul 5 (30 de puncte):$* restricţiile iniţiale.

h2. Exemplu