== 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$, mergand 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 de $1$ la $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].$

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 $v[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ă $v[i][j-1] - v[i][j-2] <= v[i][j] - v[i][j-1].$

Ajutaţi-l pe Rick să afle *costul minim* pentru ca lugimea celui mai scurt drum de la $1$ la $N$ să fie cu cel putin $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 $K$ unităţi mai mare decât era iniţial.

h2. Date de intrare

Fişierul de intrare $curcani.in$ conţine pe prima linie numerele $N$, $M$ şi $K$ reprezentând numărul de noduri, numărul de muchii, respectiv valoarea cu care trebuie marită lungimea drumului minim. Pe linia $i + 1$ $(1 ≤ i ≤ M)$ , se află $x,y,z$ separate prin câte un spaţiu, reprezentând faptul că există o muchie orientată de la $x$ la $y$ de lungime $z$. În continuare urmează $M$ linii cu câte $K$ numere reprezentând costurile de mărire ale muchiilor. Al $j$-lea element de pe linia $M + 1 + i$ reprezintă costul pentru a creste lungimea muchiei $i$ cu $j$ unităţi. ( $1 ≤ i ≤ M$, $1 ≤ j ≤ K$ )

Fişierul de intrare $curcani.in$ conţine pe prima linie numerele $N,M$ şi $K$ reprezentând numărul de noduri, numărul de muchii, respectiv valoarea cu care trebuie marită lungimea drumului minim. Pe linia $i+1$, $1 ≤ i ≤ M$, se află $x,y,lg$ separate prin câte un spaţiu, reprezentând faptul că există o muchie orientată între $x$ şi $y$ de lungime $lg$. În continuare urmează $M$ linii cu câte $K$ numere reprezentând costurile de mărire ale muchiilor. Al $j$-lea element de pe linia $m + 1 + i$ reprezintă costul să măresc muchia $i$ cu $j$ unităţi. ( $1 ≤ i ≤ M$, $1 ≤ j ≤ K$ )

h2. Date de ieşire

h2. Restricţii
* $1 ≤ K ≤ 5$

* $1 ≤ N ≤ 250$
* $1 ≤ M ≤ 1000$
* Se garantează că graful aciclic si exista cel putin un drum de la $1$ la $N$.
* $0$ $≤ A[i][j] ≤ 10^9$
* A[i][j-1] ≤ A[i][j]
* Muchiile au lungimea initiala ≤ $10^9$
* Pot exista mai multe muchii între aceeaşi pereche de noduri

* $1 ≤ N ≤ 200$
* $1 ≤ M ≤ 1000$ ??
* Se garantează că graful este conex şi aciclic

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.

* *Subtask 1 (... puncte)*
** $N ≤ 50$
** $1 ≤ K ≤ 5$
** $1 ≤ M ≤ 1000$ ??
 
* *Subtask 2 (... puncte)*
** $N ≤ 200$
** $1 ≤ K ≤ 5$
** $1 ≤ M ≤ 1000$ ??
** Graful este format din mai multe lanţuri independente de la 1 la N
 
* *Subtask 3 (... puncte)*
** $N ≤ 200$
** $1 ≤ K ≤ 5$
** $1 ≤ M ≤ 1000$ ??
** Nodurile de la $1$ la $N-1$ formează un arbore, iar toate frunzele acestuia sunt conectate de nodul $N$
 
* *Subtask 4 (... puncte)*
** $N ≤ 200$
** $K = 1$
 
* *Subtask 5 (... puncte)*
** Fără restricţii suplimentare.

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

|5 7 1
1 2 41
1 5 45
2 3 1
2 4 2
3 5 3
4 5 2
4 5 2
1
1
3
3
4
2
4
| 2
|
| 6 13 2
1 3 103
1 3 104
1 5 113
3 2 7
2 4 14
2 5 4
2 6 20
5 6 18
5 4 12
5 4 11
4 6 7
4 6 7
4 6 6
12 35
12 35
12 34
11 32
11 32
11 33
11 33
12 36
11 32
12 35
12 36
12 36
11 33
| 45

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

|
h3. Explicaţie

Pentru primul exemplu trebuie incrementate primele 2 muchii cu cate o unitate.
Pentru al doilea exemplu va trebui sa ne credeţi pe cuvânt.

...

== include(page="template/taskfooter" task_id="curcani") ==