题目描述

有一个由 $N$ 行 $N$ 列组成的网格，从上往下第 $i$ 行、从左往右第 $j$ 列的格子记为 $(i,j)$。

这些格子必须被涂成颜色 $1$ 到颜色 $C$ 中的某一种颜色，初始时 $(i,j)$ 被涂成颜色 $c_{i,j}$。

当网格满足以下条件时，称为“好网格”：对于所有满足 $1 \leq i,j,x,y \leq N$ 的格子，

• 如果 $(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}$。

求所有格子的“违和感”之和的最小可能值。

输入格式

输入从标准输入按以下格式给出：

$N$ $C$
$D_{1,1}$ $...$ $D_{1,C}$
$\dots \dots$
$D_{C,1}$ $...$ $D_{C,C}$
$c_{1,1}$ $...$ $c_{1,N}$
$\dots \dots$
$c_{N,1}$ $...$ $c_{N,N}$

输出格式

输出所有格子的“违和感”之和的最小可能值 $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)$ 重新涂成颜色 $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}$ 的情况可能存在。