题目描述

一家公司为分布在不同城镇的合作伙伴提供服务。

该公司有三名移动服务人员员工。如果某个位置发生请求，服务人员员工必须从其当前位置移动到请求的位置（如果没有员工在那里），以满足请求。任何时候只能有一名员工移动。他们只能在有请求时移动，并且不允许同时在同一位置。将员工从位置 $p$ 移动到位置 $q$ 会产生给定的成本 $C(p,q)$。成本函数未必对称，但不移动的成本为 $0$，即 $C(p,p)=0$。公司必须严格按照先来先服务的原则满足收到的请求。

目标是最小化满足给定请求序列的总成本。

输入格式

第一行一个数 $𝑇$ ，表示测试用例的数量。

每组测试用例的第一行有两个数 $𝐿,𝑁$ ，表示有 $𝐿$ 个位置和 $𝑁$ 个请求。

接下来的 $𝐿$ 行中的每一行都包含 $𝐿$ 个非负整数。其中第 $𝑖+1$ 行第 $𝑗$ 个数是 $𝑐(𝑖,𝑗)$，表示价钱。

最后一行，有 $𝑛$ 个整数，分别为 $𝑥1,\ 𝑥2,\ 𝑥3\ ...\ 𝑥𝑛$ 表示请求的位置。

最初，三名服务人员分别位于地点 $1$、$2$ 和 $3$。

输出格式

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

样例

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

5

数据范围

对于 $100\%$ 的数据满足 $3≤𝐿≤200,1≤𝑁≤1000,0≤𝑐(𝑖,𝑗)≤2000$。