AT_abc099_d [ABC099D] Good Grid

有一个 $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) \bmod 3 = (x+y) \bmod 3$，则 $(i, j)$ 和 $(x, y)$ 的颜色相同。 - 如果 $(i+j) \bmod 3 \neq (x+y) \bmod 3$，则 $(i, j)$ 和 $(x, y)$ 的颜色不同。 其中，$X \bmod Y$ 表示 $X$ 除以 $Y$ 的余数。 你可以将 $0$ 个或多个格子的颜色重新涂成任意颜色，使得网格变成“好网格”。 对于某个格子，如果涂色前的颜色是 $X$，涂色后的颜色是 $Y$，则在该格子上产生的“违和感”为 $D_{X,Y}$。 请你求出所有格子的违和感之和的最小可能值。

输入按以下格式从标准输入读入。 > $N$ $C$ > $D_{1,1}$ $...$ $D_{1,C}$ > $\vdots$ > $D_{C,1}$ $...$ $D_{C,C}$ > $c_{1,1}$ $...$ $c_{1,N}$ > $\vdots$ > $c_{N,1}$ $...$ $c_{N,N}$

当所有格子的违和感之和的最小值为 $x$ 时，输出 $x$。

### 限制条件 - $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)$ 涂成颜色 $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}$ 可能成立。 由 ChatGPT 4.1 翻译