题目描述

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$ mod $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.

有一个网格，网格中有 $N$ 行和 $N$ 列正方形。假设 $(i,j)$ 是位于从上往下第 $i$ 行和从左往上第 $j$ 列的正方形。

这些方格必须涂上从颜色 $1$ 到颜色 $C$ 的 $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$ 。

样例 #1

样例输入 #1

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

样例输出 #1

3

样例 #2

样例输入 #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

说明

数据规模与约定

• $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$
• 所有输入值均为整数。

样例 $1$ 解释

样本输出 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}$ 是可能的。