分数: 400 点
问题陈述
有一个网格 N 行和 N 方格列。让 (i,j) 是位于 i从顶部开始的第行和 j左起第 列。
这些正方形必须绘制在其中之一 C 来自 Color 的颜色 1 到颜色 C。最初, (i,j) 涂有颜色 c_{i,j}.
我们说网格是 好 当所有满足以下条件时网格 i,j,x,y 满意 1 \leq i,j,x,y \leq N:
- If (i+j) \% 3=(x+y) \% 3,颜色 (i,j) 和颜色 (x,y) 是相同的。
- If (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