Farmer John szuka łodzią legendarnego skarbu na jednej z $N$ wysp $(1 \le N \le 100)$ Cowribbean Sea, numerowanych $1,\ldots,N$.

Mapa wymaga startu w1 i końca w $N$ poprzez $A_{1}$, $A_{2}$, ..., $A_{M}$, ciąg $M$ wysp $(2 \le M \le 10,000)$, zanim skarb się pokaże. Można odwiedzać je i inne poza kolejnością i wielokrotnie, ale podróż musi zawierać $A_{i}$ w porządku mapy.

FJ unika piratów i zna niebezpieczeństwo $(0 \le danger \le 100,000)$ między każdą parą wysp. Suma dotyczy wszystkich przebytych tras.

Znajdź najbezpieczniejszą trasę po skarb zgodną z mapą.

Wejście

• Wiersz1: dwie liczby całkowite oddzielone spacją, $N$ i $M$.
• Wiersze $2,\ldots,M+1$: wiersz $i+1$ opisuje $i_{th}$ wymaganą wyspę całkowitym $A_{i}$.
• Wiersze $M+2,\ldots,N+M+1$: wiersz $i+M+1$ zawiera $N$ całkowitych oddzielonych spacją, niebezpieczeństwa od $i$ do1, 2, ..., $N$. $i$-ta jest zawsze0.

Wyjście

• Wiersz1: minimalne niebezpieczeństwo uzyskania skarbu.

Przykład

Wejście 1

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

Wyjście 1

7

Uwagi

3 wyspy i4 wizyty:1, 2, znów1, potem3. Trasy(1,2), (2,3), (3,1) i odwrotne mają5, 2, 1.

Trasa1, 3, 2, 3, 1, 3 daje7 i zawiera1, 2, 1, 3. Unikamy niebezpiecznej1–2.

Autor zadania: Jeffrey Wang, 2007