← 返回题目列表

AtCoder · abc099_d

D. 好网格

中文机器翻译题面 查看原题

分数: 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