题目描述

探险家陈明正在翡翠海域的 $N$ ($1 \le N \le 100$) 座岛屿中寻找传说中的宝藏，这些岛屿编号为 $1 \sim N$。

藏宝图告诉他，他必须按照特定的顺序 $A_1, A_2, \dots, A_M$ ($2 \le M \le 10^4$) 依次经过这些岛屿，从岛屿 $1$ 出发，最终到达岛屿 $N$，宝藏才会现身。他可以途经这些岛屿之外的其他岛屿，也可以多次经过同一座岛屿，但他的路线中必须包含按顺序排列的 $A_i$ 序列。

陈明希望尽量避开危险区域。已知每对岛屿之间的危险等级为 $(0 \le danger \le 10^5)$。整个航程的总危险等级等于他所经过的所有路径的危险等级之和。

请帮助陈明找到满足藏宝图要求的危险等级最小的航线。

输入格式

第 $1$ 行是两个用空格分隔的整数 $N$ 和 $M$。

接下来 $M$ 行，第 $i+1$ 行包含一个整数 $A_i$，表示第 $i$ 个必须经过的岛屿编号。

接下来 $N$ 行，第 $i+M+1$ 行包含 $N$ 个用空格分隔的整数，第 $i+M+1$ 行的第 $j$ 个整数表示岛屿 $i$ 与岛屿 $j$ 之间的路径危险等级。其中第 $i$ 个整数始终为 $0$。

输出格式

一行一个整数，表示陈明完成整个航程所遇到的最小危险等级。

样例

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

7

提示

本题中，有 $3$ 座岛屿，藏宝图要求按顺序经过 $4$ 座岛屿：岛屿 $1$、岛屿 $2$、岛屿 $1$、最后是岛屿 $3$。各路径的危险等级如下：路径 $(1, 2)$、$(2, 3)$、$(3, 1)$ 及其反向路径的危险等级分别为 $5$、$2$ 和 $1$。

陈明可以按照 $1 \to 3 \to 2 \to 3 \to 1 \to 3$ 的路线航行，总危险等级为 $7$。藏宝图要求的 $(1, 2, 1, 3)$ 序列被这条路线满足。通过绕行，他避免了岛屿 $1$ 和 $2$ 之间危险等级较高的直接路径。