В этой задаче прямоугольная матрица \(a\) размером \(n \times m\) называется возрастающей, если для каждой строки \(i\) при просмотре слева направо значения строго возрастают (то есть \(a_{i,1}<a_{i,2}<\dots<a_{i,m}\)) и для каждого столбца \(j\) при просмотре сверху вниз значения строго возрастают (то есть \(a_{1,j}<a_{2,j}<\dots<a_{n,j}\)).
В заданной матрице неотрицательных целых чисел надо заменить каждое значение \(0\) на некоторое положительное целое число так, чтобы получившаяся матрица была возрастающей и сумма её элементов — максимальной, или определить, что так сделать нельзя.
Гарантируется, что в заданной матрице значения все значения \(0\) содержатся только во внутренних ячейках (то есть не в первой или последней строке и не в первом или последнем столбце).
Выходные данные
Если возможно заменить все нули на положительные числа, чтобы матрица была возрастающей, выведите максимальную возможную сумму элементов матрицы. Иначе, выведите -1.
Примечание
В первом примере результирующая матрица выглядит следующим образом:
1 3 5 6 7
3 6 7 8 9
5 7 8 9 10
8 9 10 11 12
Во втором примере в среднюю ячейку обязательно надо поставить значение \(3\).
В третьем примере искомой результирующей матрицы не существует.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 5
1 3 5 6 7
3 0 7 0 9
5 0 0 0 10
8 9 10 11 12
|
144
|
|
2
|
3 3
1 2 3
2 0 4
4 5 6
|
30
|
|
3
|
3 3
1 2 3
3 0 4
4 5 6
|
-1
|
|
4
|
3 3
1 2 3
2 3 4
3 4 2
|
-1
|