D - Good Grid Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 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 を出力せよ。

入力例 1

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

出力例 1

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

入力例 2

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

出力例 2

428

Score : 400 points

Problem Statement

There is a grid with N rows and N columns of squares. Let (i,j) be the square at the i-th row from the top and the j-th column from the left.

These squares have to be painted in one of the C colors from Color 1 to Color C. Initially, (i,j) is painted in Color c_{i,j}.

We say the grid is a good grid when the following condition is met for all i,j,x,y satisfying 1 \leq i,j,x,y \leq N:

  • If (i+j) \% 3=(x+y) \% 3, the color of (i,j) and the color of (x,y) are the same.
  • If (i+j) \% 3 \neq (x+y) \% 3, the color of (i,j) and the color of (x,y) are different.

Here, X \% Y represents X modulo Y.

We will repaint zero or more squares so that the grid will be a good grid.

For a square, the wrongness when the color of the square is X before repainting and Y after repainting, is D_{X,Y}.

Find the minimum possible sum of the wrongness of all the squares.

Constraints

  • 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
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

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}

Output

If the minimum possible sum of the wrongness of all the squares is x, print x.

Sample Input 1

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

Sample Output 1

3
  • Repaint (1,1) to Color 2. The wrongness of (1,1) becomes D_{1,2}=1.
  • Repaint (1,2) to Color 3. The wrongness of (1,2) becomes D_{2,3}=1.
  • Repaint (2,2) to Color 1. The wrongness of (2,2) becomes D_{3,1}=1.

In this case, the sum of the wrongness of all the squares is 3.

Note that D_{i,j} \neq D_{j,i} is possible.

Sample Input 2

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

Sample Output 2

428