Fişierul intrare/ieşire:	curcani.in, curcani.out	Sursă	Summer Challenge 2021
Autor	Alexandru Luchianov	Adăugată de	comisia summer 2k21 •summer21
Timp execuţie pe test	0.5 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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 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 lungimea drumului minim dintre 1 şi N să fie cu K unităţi mai mare decât era iniţial.

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,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 )

Date de ieşire

În fişierul de ieşire curcani.out se va afla o singură valoare repezentând costul minim cerut.

Restricţii

• 1 ≤ K ≤ 5
• 1 ≤ N ≤ 200
• 1 ≤ M ≤ 1000 ??
• Se garantează că graful este conex şi aciclic

Subtaskuri

• 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.

Exemplu

Explicaţie

...

Cum se trimit solutii?