一家公司为其位于不同城镇的合作伙伴提供服务。公司现有流动服务人员 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）。输出任意解即可。

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

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

CEOI