Farmer John busca de barco um tesouro lendário numa das $N$ ilhas $(1 \le N \le 100)$ de Cowribbean Sea, numeradas $1,\ldots,N$.

O mapa exige começar em1, terminar em $N$ e passar por $A_{1}$, $A_{2}$, ..., $A_{M}$, sequência de $M$ ilhas $(2 \le M \le 10,000)$, antes de surgir o tesouro. Pode visitar essas e outras fora de ordem e repetidamente, mas deve incluir $A_{i}$ na ordem do mapa.

FJ evita piratas e conhece perigo $(0 \le danger \le 100,000)$ entre cada par. Total é a soma de todos os caminhos percorridos.

Ache a rota de menor perigo ao tesouro que satisfaça o mapa.

Entrada

• Linha1: dois inteiros separados por espaço, $N$ e $M$.
• Linhas $2,\ldots,M+1$: linha $i+1$ dá a $i_{th}$ ilha obrigatória pelo inteiro $A_{i}$.
• Linhas $M+2,\ldots,N+M+1$: linha $i+M+1$ tem $N$ inteiros separados por espaço, perigos de $i$ a1, 2, ..., $N$. O $i$-ésimo sempre0.

Saída

• Linha1: perigo mínimo para obter tesouro.

Exemplos

Entrada 1

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

Saída 1

7

Nota

3 ilhas e4 visitas:1, 2, novamente1, enfim3. Caminhos(1,2), (2,3), (3,1) e inversos valem5, 2, 1.

Rota1, 3, 2, 3, 1, 3 dá7 e contém1, 2, 1, 3. Evita1–2, muito perigoso.

Autor do problema: Jeffrey Wang, 2007