U88312 服务

一家公司为它在各地的用户提供服务，公司有三名负责这项工作的员工，分别编号为1,2,3，服务的地点有$n$个，分别编号为1,2,3,...$n$，把从编号为$p$的服务地点直接到达编号为$q$的服务地点所需的移动费用记为$C(p,q)$，显然$C(p,p)=0$（停留在原地不需要费用），但不保证对任意$p,q$均有$C(p,q)=C(q,p)$。 初始时员工1在地点1，员工2在地点2，员工3在地点3，现在公司依次收到了$L$个服务请求，每个请求需要一名员工赶到其指定的地点进行服务，员工可以选择直达，也可以选择经过若干个服务地点中转，特别地，如果指派的员工已在当前请求所在地，则该请求不需要任何移动费用即可被处理。 出于公平起见，所有请求必须按顺序处理，这意味着即使一名员工在赶往当前请求的途中经过之后的请求所在的地点，他也不可以先处理之后的请求，但是公司不限制每位员工赶往请求地点的路线，也允许一个服务地点有多名员工。 你的任务就是对于这$L$个请求，找到一个服务方案（即对每个请求分配合适的员工去服务以及规划移动路线），使得三名员工提供服务的总移动费用最小。

每个测试点第一行为一个正整数T，表示该测试点内的数据组数，你需要对该测试点内的T组数据都分别给出正确的答案才能获得该测试点的分数。 接下来$T$组数据，每组数据第一行两个正整数$n$和$L$，含义如题目所述，接下来$n$行，每行$n$个非负整数，其中第$p$行第$q$个数表示$C(p,q)$，最后一行包含一行$L$个正整数，依次描述每个请求指定的地点。

对每组数据输出一行一个非负整数，表示最小的总移动费用。