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

“魔力棋盘”还有一个额外的约束：仅共享一个顶点的格子必须具有不同的奇偶性（奇数与偶数）。注意，以下棋盘是无效的，因为 $2$ 和 $4$ 仅共享一个顶点且奇偶性相同：

第一个 $4 \times 4$ 的例子是一个有效的魔力棋盘。给定一个部分填充的魔力棋盘，你能否填充棋盘中剩余的位置，使得所有数值之和尽可能小？

输入格式

每个输入包含一个测试用例。注意，你的程序可能会在不同的输入上运行多次。每个输入以一行包含两个空格分隔的整数 $n$ 和 $m$ ($1 \le n, m \le 2\,000$) 开始，分别表示棋盘的行数和列数。接下来的 $n$ 行，每行包含 $m$ 个空格分隔的整数 $c$ ($0 \le c \le 2\,000$)，表示棋盘的内容。$0$ 表示需要你填充的空位。你可以使用任何正整数来填充空位，只要最终构成一个有效的魔力棋盘即可。你不受数值 $\le 2\,000$ 的限制，且数值不需要唯一。

输出格式

输出一个整数，表示通过将 $0$ 替换为正整数以构成有效魔力棋盘后，所有数值之和的最小值。如果无法通过替换 $0$ 来满足魔力棋盘的约束，则输出 $-1$。

样例

样例输入 1

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

样例输出 1

88

样例输入 2

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

样例输出 2

-1

样例输入 3

2 3
0 0 0
0 0 0

样例输出 3

18