



			EXCURSIE
		       ----------

	Ion este seful unei companii din Romania. El trebuie sa efectueze o
excursie de afaceri in Germania. Excursia lui va dura intre o saptamana si 4
saptamani. Costurile deplasarii pana in Germania si inapoi vor fi suportate
de oamenii de afaceri germani.
	Pe perioada sederii lui in Germania, Ion trebuie sa plateasca hotelul
la care este cazat si drumurile in interes de afaceri pe care le face din
orasul in care este cazat in alte orase dus-intors (drumurile sunt stabilite
din Romania, cel mult unul pe zi). Pentru a putea fi gasit de oamenii de afa-
ceri germani, Ion trebuie sa fie cazat toata saptamana intr-un oras.
	Pentru ca Ion sa poata vizita cat mai multe orase din Germania, nemtii
s-au oferit ca la sfarsit de saptamana sa-i plateasca lui Ion drumul pana in-
tr-un oras in care acesta vrea sa stea in saptamana care urmeaza.
	Compania condusa de Ion nu este bogata si de aceea Ion doreste sa aiba
cheltuieli minime, dar si sa viziteze Germania (Ion va sta intr-un oras cel
mult o saptamana).
	Alcatuiti un program care sa afiseze in fisierul de iesire costul minim
al excursiei si orasele vizitate de Ion.

	Fisierul de intrare se va numi EXCURSIE.IN si va contine:
Pe prima linie:		m		(numarul de saptamani al excursiei,1<=m<=4)
Pe a doua linie:	c[1] c[2] .. c[i] .. c[m*7]   (c[i]-orasul in care Ion
					trebuie sa ajunga in ziua i; daca c[i]=0
					ion sta la hotel in ziua i)
Pe a treia linie:	n		(numarul de orase),4<=n<=50
Pe urmatoarele n linii:
		a[1,1] a[1,2] ... a[1,n]   (a[i,j]-costul drumului direct de la
		a[2,1] a[2,2] ... a[2,n]    orasul i la orasul j)
		........................    0<=a[i,j]<=255
		a[n,1] a[n,2] ... a[n,n]
Pe urmatoarea linie:	b[1] b[2] .. b[i] .. b[n]  (b[i] - costul cazarii in timp de
					   o saptamana in orasul i, 0<=b[i]<=255)

	Fisierul de iesire se va numi EXCURSIE.OUT si va contine:
Pe prima linie:			s	(cheltuielile lui Ion pe durata excursiei)
Pe urmatoarele m linii:		o[i]	(orasul vizitat in saptamana i, pe linia i+1;
					   1<=i<=m)

EXEMPLU:
EXCURSIE.IN				EXCURSIE.OUT
2					46
1 2 3 4 0 0 0 1 2 3 4 0 0 0		4
4					3
0 2 5 6
7 0 3 3
9 10 0 2
2 3 2 0
10 9 6 2