题目描述

Alice 和 Bob 将在一个有 $N$ 行 $M$ 列的网格上玩一个游戏，其中 $M$ 是偶数。还有一个正整数 $K$。初始时，网格的每个单元格包含一个介于 $0$ 和 $K$ 之间（含两端）的值，且每个单元格都是 未标记 的。玩家轮流操作，Alice 先手。当当前玩家无法进行操作时，游戏结束。

在每位玩家的回合中，他们选择一个网格中的 未标记 单元格，以及一个介于 $0$ 和 $K$ 之间（含两端）的整数 $a$。然后，将该单元格的值设置为 $a$，并将与所选单元格同一列的所有单元格 标记（包括所选单元格本身）。

网格的 不对称度 定义为：将网格沿垂直中线进行 水平 翻转后，每一对对应单元格的值之差的绝对值之和。更形式化地，它是

$$\sum_{1 \le i \le N} \left( \sum_{1 \le j \le M/2} |g_{i,j} - g_{i,M-j+1}| \right),$$

其中 $g_{i,j}$ 表示从上往下第 $i$ 行、从左往右第 $j$ 列的单元格中的值。例如，下面的 $2 \times 4$ 网格的不对称度为 $|8-0|+|4-2|+|6-6|+|7-9|=12$。

$$\begin{array}{|c|c|c|c|} \hline 8 & 4 & 2 & 0 \\ \hline 6 & 7 & 9 & 6 \\ \hline \end{array}$$

Alice 想要在游戏结束时最小化网格的不对称度，而 Bob 想要最大化它。如果双方都采取最优策略，最终网格的不对称度是多少？

输入格式

输入的第一行包含 $3$ 个空格分隔的整数 $N$、$M$ 和 $K$（$1 \le N,M \le 2\,000$，$M$ 是偶数，$1 \le K \le 10^9$）。

接下来的 $N$ 行每行包含 $M$ 个整数，其中第 $i$ 行包含整数 $g_{i,1},\ldots,g_{i,M}$（$0 \le g_{i,j} \le K$），即从上往下第 $i$ 行从左到右的单元格的值。

输出格式

输出一个整数，表示 Alice 和 Bob 都采取最优策略时最终网格的不对称度。

3 2 1
1 0
1 0
0 0

2

1 10 21
4 2 0 6 7 6 9 9 10 21

55

4 6 986754321
219759391 882760615 762656191 423465948 621463211 136889371
215621504 385106915 740086459 417915224 551800597 572994766
176308756 365311996 635683450 907755406 590000050 586083433
607011121 457147795 837558908 684766852 946836347 303039615

3972378656

提示

样例输入 #1 的输出解释

只有 $2$ 列，因此每位玩家将进行 $1$ 次操作。由于 Alice 先手，她可以执行以下操作：

• 选择第一列中某个值为 $1$ 的单元格，将其值设为 $0$。那么 Bob 的最优操作是将同一行第二列的单元格的值设为 $1$。最终网格将与原网格类似，只是前两行中某行的 $0$ 和 $1$ 交换了位置。这样的网格不对称度为 $|1-0|+|0-1|+|0-0|=2$。
• 选择第二列前两行中的某个单元格，将其值设为 $1$。那么 Bob 的最优操作是将同一行第一列的单元格的值设为 $0$。同样，最终网格的不对称度为 $2$。
• 选择第三行中的一个单元格，将其值设为 $1$。那么 Bob 的最优操作可以是将第三行中另一个单元格的值设为 $0$。注意所选单元格原本的值就是 $0$，并且这样的操作是允许的。那么最终网格每一行都有一个 $0$ 和一个 $1$，导致不对称度为 $3$。
• 选择任意一个单元格，将其值设为其当前值。那么 Bob 的最优操作是将剩余的未标记列中第三行的单元格的值设为 $1$。最终网格每一行都有一个 $0$ 和一个 $1$，不对称度为 $3$。

我们可以看到，无论 Alice 如何操作，Bob 都能使不对称度至少为 $2$。如果 Alice 采用最优的第一步，她可以确保 Bob 无法使最终的不对称度超过 $2$。因此，双方均采取最优策略时的不对称度为 $2$。

样例输入 #2 的输出解释

只有一行，因此在每次操作中，当前玩家将选择一个未标记的单元格，并将其设为 $0$ 到 $21$ 之间（含两端）的任意值。双方各进行 $5$ 次操作后游戏结束，所有 $10$ 个单元格都被标记。

样例输入 #3 的输出解释

注意答案可能超出 $32$ 位整数的范围。

以下表格展示了可获得的 $25$ 分的分配情况：

分值	$N$ 的范围	$M$ 的范围	$K$ 的范围
$2$ 分	$N=1$	$2 \le M \le 2\,000$	$1 \le K \le 10^9$
$3$ 分	$1 \le N \le 2\,000$	$M=2$	$K=1$
	^	^	$1 \le K \le 10$
			$1 \le K \le 10^9$
$4$ 分		$2 \le M \le 2\,000$	$K=1$
		^	$1 \le K \le 10$
$6$ 分			$1 \le K \le 10^9$

翻译由 DeepSeek V4 Pro 完成