P16166 [ICPC 2015 NAIPC] Magic Checkerboard

考虑一个 $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$。

翻译由 DeepSeek V3.2 完成