题目描述

在本题中，如果一个 $n \times m$ 的矩阵 $a$ 满足：对于每一行 $i$，从左到右元素严格递增（即 $a_{i,1} < a_{i,2} < \dots < a_{i,m}$）；对于每一列 $j$，从上到下元素严格递增（即 $a_{1,j} < a_{2,j} < \dots < a_{n,j}$），则称该矩阵为递增矩阵。

现给定一个只包含非负整数的矩阵，需要将其中所有的 $0$ 替换为某个正整数，使得最终得到的矩阵是递增矩阵，并且矩阵所有元素之和最大。如果无法做到，输出 $-1$。

保证所有 $0$ 只出现在内部单元格（即不在第一行、最后一行、第一列、最后一列）。

输入格式

第一行包含两个整数 $n$ 和 $m$（$3 \le n, m \le 500$），表示矩阵 $a$ 的行数和列数。

接下来的 $n$ 行，每行包含 $m$ 个非负整数，表示矩阵的每一行：$a_{i,1}, a_{i,2}, \dots, a_{i,m}$（$0 \le a_{i,j} \le 8000$）。

保证所有 $a_{i,j}=0$ 的位置都满足 $1 < i < n$ 且 $1 < j < m$。

输出格式

如果可以将所有 $0$ 替换为正整数，使得矩阵递增，则输出矩阵元素和的最大值。否则输出 $-1$。

说明/提示

在第一个样例中，最终矩阵如下：

1 3 5 6 7
3 6 7 8 9
5 7 8 9 10
8 9 10 11 12

在第二个样例中，中间的单元格必须填 $3$。

在第三个样例中，不存在满足条件的矩阵。

由 ChatGPT 4.1 翻译

样例

4 5
1 3 5 6 7
3 0 7 0 9
5 0 0 0 10
8 9 10 11 12

144

3 3
1 2 3
2 0 4
4 5 6

30

3 3
1 2 3
3 0 4
4 5 6

-1

3 3
1 2 3
2 3 4
3 4 2

-1