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

在每位玩家的回合中，他们选择一个未被标记的单元格和一个 $0$ 到 $K$（含 $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$。

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

输入格式

第一行包含三个空格分隔的整数 $N$、$M$ 和 $K$（$1 \le N, M \le 2000$，$M$ 为偶数，$1 \le K \le 10^9$）。

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

下表显示了 25 分的分布情况：

输出格式

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

样例

样例输入 1

3 2 1
1 0
1 0
0 0

样例输出 1

2

说明 1

只有 2 列，因此每位玩家各进行 1 次移动。Alice 先手，她可以执行以下操作：

• 选择第一列中值为 1 的单元格之一，并将其值设为 0。此时 Bob 的最优策略是将第二列同一行的单元格值设为 1。最终网格将与原网格相同，仅第一列和第二列的前两行中 0 和 1 的位置发生了交换。该网格的不对称度为 $|1-0| + |0-1| + |0-0| = 2$。
• 选择第二列前两行中的一个单元格并将其值设为 1。此时 Bob 的最优策略是将第一列同一行的单元格值设为 0。同样，最终网格将与原网格相同，仅第一列和第二列的前两行中 0 和 1 的位置发生了交换。该网格的不对称度为 2。
• 选择第三行中的一个单元格并将其值设为 1。此时 Bob 的最优策略是将第三行中另一个单元格的值设为 0。注意，所选单元格原本的值就是 0，这种移动是允许的。最终网格每行将包含一个 0 和一个 1，导致不对称度为 3。
• 选择任意单元格并将其值设为当前值。此时 Bob 的最优策略是将剩余未标记列的第三行单元格值设为 1。最终网格每行将包含一个 0 和一个 1，导致不对称度为 3。

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

样例输入 2

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

样例输出 2

55

说明 2

只有一行，因此对于每次移动，当前玩家将选择一个未标记的单元格并将其设置为 0 到 21 之间的任意值。游戏在每位玩家各进行 5 次移动后结束，此时所有 10 个单元格均被标记。

样例输入 3

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

样例输出 3

3972378656

说明 3

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