C. Возрастающая матрица
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В этой задаче прямоугольная матрица $$$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$$$ содержатся только во внутренних ячейках (то есть не в первой или последней строке и не в первом или последнем столбце).

Входные данные

В первой строке записаны целые числа $$$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.

Примеры
Входные данные
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
Примечание

В первом примере результирующая матрица выглядит следующим образом: 


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

Во втором примере в среднюю ячейку обязательно надо поставить значение $$$3$$$.

В третьем примере искомой результирующей матрицы не существует.