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

输入

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

输出

3

样例 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

输出

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)$ 涂成颜色 $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 翻译