SP703 SERVICE - Mobile Service

题目描述

有一个公司有 $3$ 个流动员工。任何时刻只有一名员工可以移动，不允许同一位置上有 $2$ 个及以上员工。

每次移动需要花费，从位置 $p$ 移动到位置 $q$ 需要花费 $c(p,q)$ 的价钱。不移动不需要花费（即 $c(i,i)=0$）但不保证 $c(p,q)=c(q,p)$。

现在给出 $N$ 个请求，第 $i$ 个请求发生在位置 $x_i$。公司必须按照顺序，派一名员工到位置 $x_i$，过程中不能去其他地方，也就是必须直接过去。

$3$ 个流动员工的初始位置分别为 $1,2,3$。

求公司的最小花费。

输入格式

第一行有两个数 $L,N$ ，表示有 $L$ 个位置和 $N$ 个请求。

接下来的 $L$ 行中的每一行都包含 $L$ 个非负整数。其中第 $i+1$ 行第 $j$ 个数是 $c(i,j)$，表示价钱。

最后一行，有 $N$ 个整数，分别为 $x_1,x_2,x_3,\cdots,x_N$ 表示请求的位置。

输出格式

输出一个数，表示的最小花费。

输入输出样例 #1

输入 #1

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

输出 #1

5

说明/提示

对于 $100\%$ 的数据满足 $3 \le L \le 200,1 \le N \le 1000 ,0 \le c(i,j) \le 2000$。