题目描述

考虑一个 $n \times m$ 的棋盘。在棋盘的每个格子中放置一个正整数。棋盘每一列的值必须从上到下严格递增，每一行的值必须从左到右严格递增。

$$\begin{array}{|c|c|c|c|} \hline 1 & 2 & 3 & 4 \\ \hline 3 & 4 & 5 & 6 \\ \hline 5 & 6 & 7 & 8 \\ \hline 7 & 8 & 9 & 10 \\ \hline \end{array}$$

魔法棋盘 还有一个额外的约束条件：仅共享一个角的格子上的数字必须具有不同的奇偶性（偶数 vs 奇数）。注意，下面的棋盘是无效的，因为 $2$ 和 $4$ 仅共享一个角且具有相同的奇偶性：

$$\begin{array}{|c|c|} \hline 1 & 2 \\ \hline 4 & 6 \\ \hline \end{array}$$

第一个 $4 \times 4$ 的示例是一个有效的魔法棋盘。给定一个部分填充的魔法棋盘，你能否填充棋盘上的其余位置，使得所有值的总和尽可能小？

输入格式

每个输入包含单个测试用例。请注意，你的程序可能会在不同输入上多次运行。每个输入的第一行包含两个空格分隔的整数 $n$ 和 $m$（$1 \leq n, m \leq 2000$），分别表示棋盘的行数（$n$）和列数（$m$）。接下来的 $n$ 行，每行包含 $m$ 个空格分隔的整数 $c$（$0 \leq c \leq 2000$），表示棋盘的当前内容。$0$ 表示你需要填充的空白格子。你可以使用任意正整数填充这些空白格子，只要最终形成一个有效的魔法棋盘。你不受限于 $\leq 2000$ 的数字，并且数字不必互不相同。

输出格式

输出一个整数，表示通过将 $0$ 格子替换为正整数，以形成一个有效的魔法棋盘所可能达到的最小总和。如果无法替换 $0$ 格子以满足魔法棋盘的约束条件，则输出 $-1$。

4 4
1 2 3 0
0 0 5 6
0 0 7 8
7 0 0 10

88

4 4
1 2 3 0
0 0 5 6
0 4 7 8
7 0 0 10

-1

2 3
0 0 0
0 0 0

18

提示

翻译由 DeepSeek V3.2 完成