题目描述

在遥远的未来，人类已经可以自由穿梭于星际之间。银河系中有 $N$ 个重要的空间站，编号从 $1$ 到 $N$。你是一名星际旅行者，要从 $1$ 号空间站出发，最终到达 $N$ 号空间站。

你获得了一份古老的星图，上面记载着一条神秘的旅行路线 $A_1, A_2, \dots, A_M$。如果你的旅行轨迹中依次经过这些空间站（不一定连续经过），就能激活一个古老的星际传送门，获得传说中的宝藏。

但是，星际旅行充满了危险。每个空间站之间的航线上都可能遇到星际海盗、陨石带、黑洞等危险。经过多年的观测，科学家已经计算出任意两个空间站之间的危险指数 $D_{i,j}$（数值越大表示越危险）。

你希望在获得宝藏的前提下，使得整个旅程的总危险指数尽可能小。请你计算这个最小的总危险指数是多少。

输入格式

第一行包含两个用空格隔开的正整数 $N$ 和 $M$，分别表示空间站的数量和神秘路线中空间站的个数。

接下来 $M$ 行，每行一个整数 $A_i$，表示神秘路线中第 $i$ 个必须经过的空间站编号。保证 $A_1 = 1$，$A_M = N$。

接下来 $N$ 行，每行包含 $N$ 个用空格隔开的非负整数，其中第 $i$ 行的第 $j$ 个数表示从 $i$ 号空间站到 $j$ 号空间站的航线的危险指数。保证第 $i$ 行第 $i$ 列的数为 $0$。

输出格式

输出一行一个整数，表示在找到宝藏的前提下，整个旅程的最小总危险指数。

输入输出样例 #1

输入 #1

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

输出 #1

7

输入输出样例 #2

输入 #2

4 3
1
3
4
0 2 5 8
2 0 3 6
5 3 0 4
8 6 4 0

输出 #2

9

输入输出样例 #3

输入 #3

5 5
1
2
3
4
5
0 10 20 30 40
10 0 15 25 35
20 15 0 12 18
30 25 12 0 8
40 35 18 8 0

输出 #3

45

数据范围

对于全部数据，保证：

• $1 \leq N \leq 100$
• $2 \leq M \leq 10000$
• $0 \leq D_{i,j} \leq 100000$
• $D_{i,i} = 0$
• $A_1 = 1$，$A_M = N$
• 注意：$D_{i,j}$ 不一定等于 $D_{j,i}$，即危险指数可能不对称