CF1231C Increasing Matrix

在本题中，如果一个 $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 翻译