题目描述

一家公司为其位于不同城镇的合作伙伴提供服务。公司现有流动服务人员 $3$ 名。如果服务请求发生在某个位置，服务人员必须从他当前的位置移动到请求的位置（如果没有员工在那里）以满足请求。任何时候只有一名员工可以移动。他们只能应要求移动，并且不允许多名员工在同一位置。将员工从位置 $p$ 移动到位置 $q$ 会产生一定的成本 $C(p,q)$。成本计算不一定是对等的，但不动代价为 $0$，即 $C(p,p)=0$。公司必须以严格按照先请求先得服务的原则满足收到的要求。
请您编写一个程序，该程序决定服务人员中的哪位员工要为每个请求移动，以便为给定的请求列表提供服务的总成本尽可能小。

输入格式

第一行包含两个整数 $L$ 和 $N$。$L$ 是表示位置的数，$N$ 是请求数。位置由从 $1$ 到 $L$ 的整数表示。接下来的 $L$ 行中的每一行都包含 $L$ 个非负整数。第 $i+1$ 行第 $j$ 个数字是成本 $C(i,j)$。最后一行包含 $N$ 个整数，为请求列表。请求由发生请求的位置的标识符标识。起初，三名服务人员分别位于位置 $1,2$ 和 $3$，并以此为三名服务人员进行标识。

输出格式

第一行包含一个整数 $M$，它是为请求的列表提供服务的最小总成本。第二行正好包含 $N$ 个整数。第 $i$ 个编号是将为第 $i$ 个请求提供服务的服务人员的标识符（$1,2$ 或 $3$）。

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
1 2 1 2 2 1 3 1 3 

提示

数据规模与约定

对于 $100 \%$ 的数据，$3 \leq L \leq 200$，$1 \leq N \leq 1000$，$C(i,j) <2000$。

题目说明

来源于 CENTRAL-EUROPEAN OLYMPIAD IN INFORMATICS 2005 的 Mobile Service。
由