Score : $400$ points

问题描述

存在一个包含 $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$ 取模的结果。

我们需要重新涂色零个或多个方格，使得网格变为一个好网格。

对于一个方格来说，如果在重新涂色前其颜色为 $X$，重新涂色后颜色为 $Y$，则它的“不匹配度”为 $D_{X,Y}$。

求所有方格不匹配度之和的最小可能值。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 17:19:34