In this problem, a n × m rectangular matrix a is called increasing if, for each row of i, when go from left to right, the values strictly increase (that is, a_{i,1}<a_{i,2}<...<a_{i,m}) and for each column j, when go from top to bottom, the values strictly increase (that is, a_{1,j}<a_{2,j}<...<a_{n,j}).

In a given matrix of non-negative integers, it is necessary to replace each value of 0 with some positive integer so that the resulting matrix is increasing and the sum of its elements is maximum, or find that it is impossible.

It is guaranteed that in a given value matrix all values of 0 are contained only in internal cells (that is, not in the first or last row and not in the first or last column).

Input

The first line contains integers n and m (3 ≤ n, m ≤ 500) — the number of rows and columns in the given matrix a.

The following lines contain m each of non-negative integers — the values in the corresponding row of the given matrix: a_{i,1}, a_{i,2}, ..., a_{i,m} (0 ≤ a_{i,j} ≤ 8000).

It is guaranteed that for all a_{i,j}=0, 1 < i < n and 1 < j < m are true.

Output

If it is possible to replace all zeros with positive numbers so that the matrix is increasing, print the maximum possible sum of matrix elements. Otherwise, print -1.

Examples

Input


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


Output


144


Input


3 3
1 2 3
2 0 4
4 5 6


Output


30


Input


3 3
1 2 3
3 0 4
4 5 6


Output


-1


Input


3 3
1 2 3
2 3 4
3 4 2


Output


-1

Note

In the first example, the resulting matrix is as follows: 
    
    
      
    1 3 5 6 7  
    3 6 7 8 9  
    5 7 8 9 10  
    8 9 10 11 12  
    

In the second example, the value 3 must be put in the middle cell.

In the third example, the desired resultant matrix does not exist.
#(っ◔◡◔)っ ♥ GLHF ♥
import os                                                                            #(っ◔◡◔)っ
import sys                                                                           #(っ◔◡◔)っ
from io import BytesIO, IOBase                                                       #(っ◔◡◔)っ
def main():                                                                          #(っ◔◡◔)っ
    line = input().split()
    n, m = int(line[0]), int(line[1])

    arr = []
    pos = []

    for i in range(n):
        line = input().split()
        x = []
        for j in range(m):
            x.append(int(line[j]))
        arr.append(x)

    for i in range(1, n):
        for j in range(1, m):
            if arr[i][j] == 0:
                pos.append([i, j])
                arr[i][j] = max(arr[i][j-1], arr[i-1][j])

    pos.reverse()

    for i, j in pos:
        arr[i][j] = min(arr[i+1][j], arr[i][j+1]) - 1
    # print(arr)

    # checking starts
    flag1 = 0
    flag2 = 0
    for i in range(n):
        val = arr[i][0]
        for x in range(1, m):
            if arr[i][x] > val:
                val = arr[i][x]
            else:
                flag1 = 1
                break
        if flag1 == 1:
            break
    
    for i in range(m):
        val = arr[0][i]
        for j in range(1, n):
            if arr[j][i] > val:
                val = arr[j][i]
            else:
                flag2 = 1
                break
        if flag2 == 1:
            break
    if (flag1 == 1) or (flag2 == 1):
        print('-1')
    else:
        summ = 0
        for i in arr:
            summ += sum(i)
        print(summ)
            

    


BUFSIZE = 8192                                                                       #(っ◔◡◔)っ
class FastIO(IOBase):                                                                #(っ◔◡◔)っ
    newlines = 0                                                                     #(っ◔◡◔)っ
    def __init__(self, file):                                                        #(っ◔◡◔)っ
        self._fd = file.fileno()                                                     #(っ◔◡◔)っ
        self.buffer = BytesIO()                                                      #(っ◔◡◔)っ
        self.writable = "x" in file.mode or "r" not in file.mode                     #(っ◔◡◔)っ
        self.write = self.buffer.write if self.writable else None                    #(っ◔◡◔)っ
    def read(self):                                                                  #(っ◔◡◔)っ
        while True:                                                                  #(っ◔◡◔)っ
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))          #(っ◔◡◔)っ
            if not b:                                                                #(っ◔◡◔)っ
                break                                                                #(っ◔◡◔)っ
            ptr = self.buffer.tell()                                                 #(っ◔◡◔)っ
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)      #(っ◔◡◔)っ
        self.newlines = 0                                                            #(っ◔◡◔)っ
        return self.buffer.read()                                                    #(っ◔◡◔)っ
    def readline(self):                                                              #(っ◔◡◔)っ
        while self.newlines == 0:                                                    #(っ◔◡◔)っ
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))          #(っ◔◡◔)っ
            self.newlines = b.count(b"\n") + (not b)                                 #(っ◔◡◔)っ
            ptr = self.buffer.tell()                                                 #(っ◔◡◔)っ
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)      #(っ◔◡◔)っ
        self.newlines -= 1                                                           #(っ◔◡◔)っ
        return self.buffer.readline()                                                #(っ◔◡◔)っ
    def flush(self):                                                                 #(っ◔◡◔)っ
        if self.writable:                                                            #(っ◔◡◔)っ
            os.write(self._fd, self.buffer.getvalue())                               #(っ◔◡◔)っ
            self.buffer.truncate(0), self.buffer.seek(0)                             #(っ◔◡◔)っ
class IOWrapper(IOBase):                                                             #(っ◔◡◔)っ
    def __init__(self, file):                                                        #(っ◔◡◔)っ
        self.buffer = FastIO(file)                                                   #(っ◔◡◔)っ
        self.flush = self.buffer.flush                                               #(っ◔◡◔)っ
        self.writable = self.buffer.writable                                         #(っ◔◡◔)っ
        self.write = lambda s: self.buffer.write(s.encode("ascii"))                  #(っ◔◡◔)っ
        self.read = lambda: self.buffer.read().decode("ascii")                       #(っ◔◡◔)っ
        self.readline = lambda: self.buffer.readline().decode("ascii")               #(っ◔◡◔)っ
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)                  #(っ◔◡◔)っ
input = lambda: sys.stdin.readline().rstrip("\r\n")                                  #(っ◔◡◔)っ
if __name__ == "__main__":                                                           #(っ◔◡◔)っ
    main()                                                                           #(っ◔◡◔)っ
#██╗░░░██╗██╗██████╗░██████╗░██╗░░██╗
#██║░░░██║██║██╔══██╗╚════██╗██║░██╔╝
#╚██╗░██╔╝██║██║░░██║░░███╔═╝█████═╝░
#░╚████╔╝░██║██║░░██║██╔══╝░░██╔═██╗░
#░░╚██╔╝░░██║██████╔╝███████╗██║░╚██╗
#░░░╚═╝░░░╚═╝╚═════╝░╚══════╝╚═╝░░╚═╝