Farmer John sucht per Boot einen sagenhaften Schatz auf einer der $N$ Inseln $(1 \le N \le 100)$ im Cowribbean Sea, nummeriert $1,\ldots,N$.

Die Karte fordert eine Reise von1 nach $N$ über die Folge $A_{1}$, $A_{2}$, ..., $A_{M}$ aus $M$ Inseln $(2 \le M \le 10,000)$, bevor der Schatz erscheint. Er darf diese und andere ungeordnet und mehrfach besuchen, muss aber $A_{i}$ in Kartenreihenfolge enthalten.

FJ will Piraten vermeiden und kennt Gefahr $(0 \le danger \le 100,000)$ zwischen jedem Inselpaar. Gesamtgefahr ist die Summe aller durchfahrenen Wege.

Finde die ungefährlichste Schatzroute, die die Karte erfüllt.

Eingabe

• Zeile1: zwei durch Leerzeichen getrennte ganze Zahlen $N$ und $M$.
• Zeilen $2,\ldots,M+1$: Zeile $i+1$ beschreibt die $i_{th}$ Pflichtinsel mit einer ganzen Zahl $A_{i}$.
• Zeilen $M+2,\ldots,N+M+1$: Zeile $i+M+1$ hat $N$ durch Leerzeichen getrennte ganze Zahlen, Gefahren von $i$ nach1, 2, ..., $N$. Die $i$-te ist immer0.

Ausgabe

• Zeile1: minimale Gefahr zum Schatz.

Beispiele

Eingabe 1

3 4
1
2
1
3
0 5 1
5 0 2
1 2 0

Ausgabe 1

7

Hinweis

3 Inseln,4 Pflichtbesuche:1, 2, wieder1, schließlich3. Wege(1,2), (2,3), (3,1) und Rückwege haben5, 2, 1.

Route1, 3, 2, 3, 1, 3 hat Gefahr7 und enthält1, 2, 1, 3. Der gefährliche Weg1–2 wird vermieden.

Aufgabenautor: Jeffrey Wang, 2007