题目描述

有一个 $N$ 行 $N$ 列的网格，每个方格可以被涂上 $C$ 种颜色之一，颜色编号从 $1$ 到 $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}$。

求所有方格的错误值的最小可能总和。

约束条件

• $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$
• 输入中的所有值都是整数。

输入

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

$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

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

示例输出1

3

• 将 $(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}$ 是可能的。

示例输入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