Farmer John busca en barco tesoro legendario en una de $N$ islas $(1 \le N \le 100)$ de Cowribbean Sea, numeradas $1,\ldots,N$.
El mapa exige salir de1, acabar en $N$ y pasar por $A_{1}$, $A_{2}$, ..., $A_{M}$, secuencia de $M$ islas $(2 \le M \le 10,000)$, antes de aparecer el tesoro. Puede visitar estas u otras fuera de orden y repetirlas, pero debe incluir $A_{i}$ en orden del mapa.
FJ evita piratas y conoce peligro $(0 \le danger \le 100,000)$ de cada par de islas. Total es la suma de todos los caminos recorridos.
Halla la ruta de menor peligro al tesoro cumpliendo el mapa.
Entrada
- Línea1: dos enteros separados por espacio, $N$ y $M$.
- Líneas $2,\ldots,M+1$: línea $i+1$ da la $i_{th}$ isla obligatoria por el entero $A_{i}$.
- Líneas $M+2,\ldots,N+M+1$: línea $i+M+1$ contiene $N$ enteros separados por espacio, peligros de $i$ a1, 2, ..., $N$. El $i$-ésimo siempre0.
Salida
- Línea1: peligro mínimo al obtener tesoro.
Ejemplos
Entrada 1
3 4 1 2 1 3 0 5 1 5 0 2 1 2 0
Salida 1
7
Nota
3 islas y4 visitas:1, 2, otra vez1, luego3. Caminos(1,2), (2,3), (3,1) y reversos valen5, 2, 1.
Ruta1, 3, 2, 3, 1, 3 da7 y cumple1, 2, 1, 3. Evitamos el peligro alto de1–2.
Autor del problema: Jeffrey Wang, 2007