配点 : $400$ 点

問題文

$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}$ です。

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

制約

• $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$
• 入力は全て整数

入力

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

$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$ を出力せよ。

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

3

• $(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}$ である場合に注意してください。

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