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.
import java.util.Scanner;

public class Increasing_Matrix {
    public static void main(String[] args){
        long startTime = System.nanoTime();
        /*int[][] matrix={{101,  118,  122,  131,  141,  151,  165,  170,  181,  199,  209,  218,  226,  236},
                        {119,  128,  139,  147,  150,  163,  172,  184,  192,  206,  213,  225,  231,  242},
                        {126,  137,  143,  153,  161,  173,  184,  197,  207,  213,  225,  236,  241,  250},
                        {138,  147,  158,  163,  175,  189,  198,  206,  219,  227,  238,  247,  259,  262},
                        {147,  157,  165,  172,  184,  193,  207,  212,  226,  231,  240,  254,  261,  273},
                        {150,  168,  178,  186,  190,  209,  218,  220,  239,  244,  251,  260,  275,  289},
                        {166,  177,  185,  192,  202,  210,  226,  239,  246,  259,  262,  276,  289,  295},
                        {176,  182,  192,  203,  211,  221,  235,  244,  255,  263,  272,  285,  291,  307},
                        {181,  199,  208,  219,  222,  234,  242,  258,  267,  273,  288,  294,  304,  316},
                        {193,  204,  215,  223,  232,  247,  250,  260,  276,  286,  296,  302,  316,  327},
                        {205,  210,  221,  239,  248,  259,  261,  274,  288,  292,  300,  312,  326,  334},
                        {213,  222,  239,  243,  252,  261,  271,  280,  290,  308,  310,  322,  336,  342},
                        {228,  230,  249,  253,  267,  278,  288,  293,  306,  315,  325,  337,  341,  358},
                        {231,  247,  257,  260,  279,  285,  299,  301,  317,  327,  334,  340,  358,  363}};
        //Creating a Patch of Zeroes
        int patchStartRow = 9;
        int patchStartCol = 8;
        int patchRowSize = 4;
        int patchColSize = 5;
        int[][] patch_matrix=createPatch(matrix,patchStartRow,patchStartCol,patchRowSize,patchColSize);
        print_matrix(patch_matrix);
        System.out.println();
        print_matrix(fillPatchMatrix(patch_matrix));
        */
        /*int rows = 3000;
        int cols = 3000;
        int[][] matrix = new int[rows][cols];
        //Filling a matrix
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                matrix[i][j] = ((i + j) * randInt(0,1)+100);
            }
        }
        //Settings some random positions to zero
        int count = randInt(4000000, 7000000);
        for (int i = 0; i < count; i++) {
            matrix[randInt(1, rows - 2)][randInt(1, cols - 2)] = 0;
        }
        System.out.println("The total number of zeroes is " + count);*/
        /*int[][] matrix={{1, 1,1},
        {1, 1,1},
        {1, 1,1}};*/
        Scanner scan = new Scanner(System.in);
        int rows=scan.nextInt();
        int cols=scan.nextInt();
        int[][] matrix=new int[rows][cols];
        //Scan Matrix
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                matrix[i][j]=scan.nextInt();
            }
        }
        //Start patching the matrix //Print sum of all matrix elements if success else Handles any error in patching
        long sum = sum_matrix(fillPatchMatrix(matrix));
        //System.out.println("Sum is "+sum);
        //Validating the entire matrix if matrix is increasing
        int status=0;
        if(sum>0) status=validateMatrix(matrix);
        //System.out.println("Status is "+status);
        //If Invalid, then print out
        if(status<0||sum<0) {if (status<0) {System.out.println(status);} else System.out.println(sum);}
        else System.out.println(sum);
        long endTime=System.nanoTime();
        //System.out.println("Total Time elapsed is "+(endTime-startTime)/1000);
    }


    //To create a patch of zeroes of any given size
    private static int[][] createPatch(int[][] matrix,int patchStartRow,int patchStartCol,int patchRowSize,int patchColSize){
        for(int i=0;i<patchRowSize;i++){
            for(int j=0;j<patchColSize;j++){
                matrix[patchStartRow+i][patchStartCol+j]=0;
            }
        }
        return matrix;
    }


    //To fill a matrix with zeroes such that sum is maximum. We start from bottom right
    private static int[][] fillPatchMatrix(int[][] matrix){
        int rows=matrix.length;
        int cols=matrix[0].length;
        //Starting from bottom right and moving diagonally
        for(int k=rows+cols-2;k>=2;k--){
            int j=Math.min(k-1,cols-2);
            int i=k-j;
            while(j>=1 && i<=rows-2){
                if (matrix[i][j]==0) {
                    matrix[i][j] = Math.min(matrix[i + 1][j], matrix[i][j + 1]) - 1;
                    //System.out.println("Location [" + i + "][" + j + "] is zero. Set as " + matrix[i][j]);
                    //Validate if patch is successful
                    if(matrix[i][j]<=matrix[i-1][j]||matrix[i][j]<=matrix[i][j-1]){
                        matrix[i][j]= -1;
                        int[][] submatrix=new int[3][3];
                        for(int p=0;p<3;p++){
                            for(int q=0;q<3;q++){
                                submatrix[p][q]=matrix[i+p-1][j+q-1];
                            }
                        }
                        return submatrix;
                    }
                }
                j--;i++;
            }
        }
        return matrix;
    }


    //To validate if matrix is in ascending order
    private static int validateMatrix(int[][] matrix){
        int rows=matrix.length;
        int cols=matrix[0].length;
        //boolean status=true;
        int[] location=new int[2];
        int i=1;int j=1;
        for (i=0;i<rows;i++){
            for(j=0;j<cols-1;j++){
                if(matrix[i][j]>=matrix[i][j+1]){
                    location[0]=i;
                    location[1]=j;
                    return -1;
                }
            }
        }
        for (j=0;j<cols;j++){
            for(i=0;i<rows-1;i++){
                if(matrix[i][j]>=matrix[i+1][j]){
                    location[0]=i;
                    location[1]=j;
                    return -1;
                }
            }
        }
        return 0;
        //else System.out.println("The matrix is invalid. Invalid location is[" + location[0] + "][" + location[1] + "]");
    }


    //To print an area of matrix
    private static void print_matrix_area(int[][] matrix, int MinRow,int MaxRow, int MinCol,int MaxCol) {
        System.out.println();
        for (int i = MinRow; i <= MaxRow; i++) {
            System.out.print("{");
            for (int j = MinCol; j <= MaxCol; j++) {
                System.out.print(matrix[i][j] + ",  ");
            }
            System.out.println("},");
        }
    }


    //To print full matrix
    private static void print_matrix(int[][] matrix) {
        int rows=matrix.length;
        int cols=matrix[0].length;
        System.out.println();
        for (int i = 0; i <rows ; i++) {
            System.out.print("{");
            for (int j = 0; j <cols; j++) {
                System.out.print(matrix[i][j] + ",  ");
            }
            System.out.println("},");
        }
    }


    //To print Sum of Matrix
    private static long sum_matrix(int[][] matrix){
        int rows=matrix.length;
        int cols=matrix[0].length;
        long sum=0;
        int i,j;
        for (i=0;i<rows;i++) {
            for (j = 0; j < cols; j++) {
                if(matrix[i][j]==-1) return -1;
                sum += matrix[i][j];
            }
        }
        return sum;
    }


    //To generate a random Number
    public static int randInt(int min, int max) {
        int randomNum = (min + (int) (Math.random() * ((max - min) + 1)));
        return randomNum;
    }
}
