题目描述

给出一个 $N\times N$ 的矩阵，$c_{i,j}\in[1,C]$。

定义一个好的矩阵满足：

• 若 $i+j\equiv x+y\ (\text{mod}\ 3)$，有 $c_{i,j}=c_{x,y}$
• 若 $i+j\not\equiv x+y\ (\text{mod}\ 3)$，有 $c_{i,j}\ne c_{x,y}$

你可以随意更改矩阵使其变成好的矩阵（更改后仍有 $c'_{i,j}\in[1,C]$）。

若将一个数字 $X$ 改为 $Y$，会造成 $D_{X,Y}$ 的错误值。

请你求出使得错误值之和最小的修改方案，输出其错误值。

输入格式

第一行两个正整数 $N, C$，$1 \leq N \leq 500$，$3 \leq C \leq 30$。

接下来是一个 $C \times C$ 的矩阵，。

接下来是一个 $N \times N$ 的矩阵，$1 \leq D_{i,j} \leq 1000\ (i \neq j),\ D_{i,j}=0\ (i=j)$，$1 \leq c_{i,j} \leq C$。

输出格式

输出使得错误值之和最小的修改方案的其错误值。

2 3
0 1 1
1 0 1
1 4 0
1 2
3 3

3

4 3
0 12 71
81 0 53
14 92 0
1 1 2 1
2 1 1 2
2 2 1 3
1 1 2 2

428