题目描述

$N$ 行 $N$ 列からなるグリッドがあり、上から $i$ 行目の左から $j$ 列目のマスを $(i,j)$ とします。

これらのマスは色 $1$ から 色 $C$ までのいずれかの色で塗られていなければならず、はじめに $(i,j)$ は色 $c_{i,j}$ で塗られています。

グリッドが、$1\ \leq\ i,j,x,y\ \leq\ N$ を満たす任意の $i,j,x,y$ に対して以下の条件を満たす場合、良いグリッドであるとします。

• $(i+j)\ \%\ 3=(x+y)\ \%\ 3$ ならば $(i,j)$ の色と $(x,y)$ の色は同じ
• $(i+j)\ \%\ 3\ \neq\ (x+y)\ \%\ 3$ ならば $(i,j)$ の色と $(x,y)$ の色は異なる

ただし、$X\ \%\ Y$ は $X$ を $Y$ で割った余りを表すこととします。

グリッドが良いグリッドになるように $0$ 個以上のマスを塗り替えます。

あるマスにおいて、塗り替える前の色が $X$ であり、塗り替えた後の色が $Y$ である場合に感じる、そのマスに対して感じる違和感は $D_{X,Y}$ です。

すべてのマスに対して感じる違和感の和のとりうる最小値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $C$ $D_{1,1}$ $...$ $D_{1,C}$ $:$ $D_{C,1}$ $...$ $D_{C,C}$ $c_{1,1}$ $...$ $c_{1,N}$ $:$ $c_{N,1}$ $...$ $c_{N,N}$

输出格式

すべてのマスに対して感じる違和感の和のとりうる最小値が $x$ のとき、$x$ を出力せよ。

题目大意

给出一个 $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}$ 的 错误值

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

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

提示

制約

• $1\ \leq\ N\ \leq\ 500$
• $3\ \leq\ C\ \leq\ 30$
• $ 1\ \leq\ D_{i,j}\ \leq\ 1000\ (i\ \neq\ j),D_{i,j}=0\ (i=j) $
• $1\ \leq\ c_{i,j}\ \leq\ C$
• 入力は全て整数

Sample Explanation 1

- $(1,1)$ を色 $2$ に塗り替えます。$(1,1)$ に対して感じる違和感は $D_{1,2}=1$ となります。 - $(1,2)$ を色 $3$ に塗り替えます。$(1,2)$ に対して感じる違和感は $D_{2,3}=1$ となります。 - $(2,2)$ を色 $1$ に塗り替えます。$(2,2)$ に対して感じる違和感は $D_{3,1}=1$ となります。 このとき、すべてのマスに対して感じる違和感の和は $3$ です。 なお、$D_{i,j}\ \neq\ D_{j,i}$ である場合に注意してください。