← 返回题目列表

Codeforces · 1231/C

C. 增加矩阵

中文机器翻译题面 查看原题

在此问题中,如果对于 $$$i$$$ 的每一行,从左到右,值严格增加(即 $$$a_{i,1}<a_{i,2}<\dots<a_{i,m}$$$),并且对于每列 $$$j$$$,当从从上到下,值严格递增(即 $$$a_{1,j}<a_{2,j}<\dots<a_{n,j}$$$)。

在给定的非负整数矩阵中,需要将 $$$0$$$ 的每个值替换为某个正整数,使得所得矩阵递增且其元素之和最大,否则发现这是不可能的。

保证在给定值矩阵中 $$$0$$$ 的所有值仅包含在内部单元格中(即不在第一行或最后一行中,也不在第一列或最后一列中)。

输入

第一行包含整数 $$$n$$$ 和 $$$m$$$ ($$$3 \le n, m \le 500$$$) — 给定矩阵 $$$a$$$ 中的行数和列数。

以下行包含每个非负整数 $$$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$$$ 为真。

输出

如果可以用正数替换所有零以使矩阵递增,则打印矩阵元素的最大可能和。否则,打印-1。

示例

输入 #1

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

输出 #1

144

输入 #2

3 3
1 2 3
2 0 4
4 5 6

输出 #2

30

输入 #3

3 3
1 2 3
3 0 4
4 5 6

输出 #3

-1

输入#4

3 3
1 2 3
2 3 4
3 4 2

输出#4

-1

注意

在第一个示例中,生成的矩阵如下:

在第二个示例中,值 $$$3$$$ 必须放在中间单元格中。

在第三个示例中,所需的结果矩阵不存在。