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$ 。

求公司的最小花费。

输入格式

第一行一个数 $T$ ，表示数据组数。

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

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

最后一行，有 $n$ 个整数，分别为 $x_1,x_2,x_3 ... x_n$ 表示请求的位置。

输出格式

一行一个数，表示每组数据的最小花费。

数据范围与说明

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

样例 #1

样例输入 #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