Na planeti X postoji N država i svaka ima po M gradova. Dva grada iz neke države mogu biti povezana jednosmernim putem. Povezanost gradova u nekoj državi određena je težinskom matricom. Ovakva matrica je dimenzija M*M i vrednost u matrici na mestu sa koordinatama (i, j) je dužina (u kilometrima) puta koji vodi od grada i do grada j. Ako ne postoji put koji vodi od grada i do grada j onda je na mestu (i, j) u matrici vrednost 0. Postoje još i međunarodni putevi koji su jednosmerni sa osobinom, da međunarodni put povezuje neki grad iz zemlje i (1 ≤ i ≤ N-1) sa nekim gradom iz zemlje i+1 i to tako da je smer puta od zemlje i ka zemlji i+1. Između bilo koje dve uzastopne zemlje i (1 ≤ i ≤ N-1) i i+1 postoji tačno K međunarodnih puteva. Dužina svakog puta je manja od 10000 kilometara.

Potrebno je startujući iz bilo kog grada na planeti X obići sve gradove na zadatoj planeti tako da se svaki grad poseti tačno jednom i da dužina tako napravljene putanje bude minimalna moguća.

Ulaz:

U prvom redu standardnog ulaza nalaze se tri broja N, M i K međusobno razdvojena razmakom (2 ≤ N ≤ 100, M ≤ 8, K ≤ M²). Zatim je u narednih M redova zadata težinska matrica prve zemlje (u svakom redu po jedna vrsta matrice). U narednih K redova zadate su međunarodne veze između gradova prve i druge zemlje po formatu grad_prve_zemlje grad_druge_zemlje dužina_veze_u_kilometrima. Zatim je zadata težinska matrica druge zemlje pa međunarodne veze između gradova druge i treće zemlje i tako dalje zaključno sa težinskom matricom N te zemlje.

Izlaz:

U prvom i jedinom redu standardnog izlaza treba ispisati dužinu tražene putanje minimalne moguće dužine.

Primer:

2 3 3
0 1 0
0 0 1
4 0 0
1 1 20
2 1 2
3 2 10
0 0 2
0 1 1
1 2 0

11

Objašnjenje: