[JSOI2010]Express Service 快递服务

「飞奔」快递公司与市内许多中小企业签订了邮件收送服务契约。由于部分公司位于同一栋大楼内，公司共设置了至多 $m$ 个收件地点，编号为 $1,2,\ldots,m$ 。

公司现有 $3$ 辆货车和 $3$ 名司机。每天早上， $3$ 名司机分别从收件地点 $1$ 、 $2$ 、 $3$ 出发。根据服务契约，公司必须在客户提出邮件寄送要求的次日，派司机前往相应地点收件。客户需要提前一天在收件服务网站上登记，公司则会在晚上安排次日的收件路线。

所有收件请求必须按照客户登记的先后顺序处理。每个请求可以交由任意一名司机完成，但对于同一名司机，其负责的请求必须按照这些请求在登记序列中的先后顺序完成。因此，一名司机可能需要在不同时间重复前往同一地点，不同司机也可能在不同时间前往同一地点。

例如，若收件地点依次为 $4,2,4,1,5,4,3,2,1$ ，虽然司机 $1$ 最初位于地点 $1$ ，但他不能在前三个请求尚未处理时，提前完成序列中第 $4$ 个、位于地点 $1$ 的请求。如果前三个请求均由司机 $2$ 或司机 $3$ 负责，那么司机 $1$ 就可以先完成第 $4$ 个请求，再继续处理后续分配给他的请求。

不要求每辆车都必须执行收件任务，最优方案可能只需出动 $1$ 辆或 $2$ 辆车。

请计算按照上述规则完成当天所有收件请求所需的最少总耗油量。

输入格式

第一行包含一个整数 $m$ ，表示收件地点的数量。各地点使用 $1$ 至 $m$ 的整数编号。

接下来 $m$ 行描述耗油量矩阵 $D$ 。其中，第 $i$ 行的第 $j$ 个整数为 $D(i,j)$ ，表示司机从收件地点 $i$ 直接行驶到收件地点 $j$ 所需的耗油量。

最后一行包含一个整数序列，按照登记顺序给出所有收件请求对应的地点编号。

输入中任意两个相邻的整数之间以一个空格分隔。

矩阵 $D$ 满足三角不等式：

D(i,j)\le D(i,k)+D(k,j)

因此，司机前往下一个收件地点时可以直接到达，无需绕道经过其他地点。

输出格式

输出一个整数，表示完成所有收件请求所需的最少总耗油量。

样例输入

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

样例输出

数据范围

$3\le m\le 200$ ；
收件请求的数量不超过 $1000$ ；
$D(i,j)\le \mathrm{maxint}$ ；
对于任意 $1\le i,j,k\le m$ ，均有 $D(i,j)\le D(i,k)+D(k,j)$ 。

来源与许可

本题为 JSOI 2010 试题「快递服务」，题面与测试数据整理自 BZOJ。

样例 1

输入

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