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.io.PrintWriter;
import java.util.*;

public class TP {

    public static PrintWriter out = new PrintWriter(System.out);
    public static Scanner in = new Scanner(System.in);

    public static void main(String[] args) {
        long s = System.currentTimeMillis();
        int t = 1;
//        t = ni();
        while (t-- > 0) solve();
        out.flush();
        tr(System.currentTimeMillis() - s + "ms");
    }

    private static void solve() {
        int n = ni(), m = ni();
        int MAX = 8000;
        int[][] a = new int[n][m];
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) a[i][j] = ni();
        if (a[n - 1][m - 1] == 0) a[n - 1][m - 1] = MAX;
        int sum = 0;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                if (a[i][j] == 0)
                    if (i == n - 1) {
                        a[i][j] = a[i][j + 1] - 1;
                    } else {
                        a[i][j] = Math.min(a[i][j + 1], a[i + 1][j]) - 1;
                    }
                sum += a[i][j];
            }
        }
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < m - 1; j++) {
                if (a[i][j] >= a[i + 1][j] || a[i][j] >= a[i][j + 1]) {
                    System.out.println(-1);
                    return;
                }
            }
        }
        for (int i = 0; i < m - 1; i++) {
            if (a[n - 1][i] >= a[n - 1][i + 1]) {
                System.out.println(-1);
                return;
            }
        }
        for (int i = 0; i < n - 1; i++) {
            if (a[i][m - 1] >= a[i + 1][m - 1]) {
                System.out.println(-1);
                return;
            }
        }
        System.out.println(sum);
    }

    private static long lcm(long a, long b) {
        return a * b / gcd(a, b);
    }

    public static int[][] enumPrimesAndLPF(int n) {
        int[] lpf = new int[n + 1];
        double lu = Math.log(n + 32);

        int tot = 0;
        int[] primes = new int[(int) ((n + 32) / lu + (n + 32) / lu / lu * 1.5)];

        for (int i = 2; i <= n; i++) {
            lpf[i] = i;
        }

        for (int p = 2, tmp; p <= n; p++) {
            if (lpf[p] == p) {
                primes[tot++] = p;
            }
            for (int i = 0; i < tot && primes[i] <= lpf[p] && (tmp = primes[i] * p) <= n; i++) {
                lpf[tmp] = primes[i];
            }
        }

        return new int[][]{Arrays.copyOf(primes, tot), lpf};
    }

    static boolean isPrime(int n) {
        for (int i = 2; i * i <= n; i++) if (n % i == 0) return false;
        return true;
    }

    static boolean sorted(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            if (a[i] > a[i + 1]) return false;
        }
        return true;
    }

    public static long gcd(long a, long b) {
        while (b != 0) {
            a %= b;
            long t = a;
            a = b;
            b = t;
        }
        return a;
    }

    private static int ni() {
        return in.nextInt();
    }

    private static String ns() {
        return in.next();
    }

    private static int[] na(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = ni();
        return a;
    }

    private static long[] nal(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = nl();
        return a;
    }

    private static long nl() {
        return in.nextLong();
    }

    private float nf() {
        return in.nextFloat();
    }

    private static double nd() {
        return in.nextDouble();
    }

    public static int[] facs(int n, int[] primes) {
        int[] ret = new int[9];
        int rp = 0;
        for (int p : primes) {
            if (p * p > n) break;
            int i;
            i = 0;
            while (n % p == 0) {
                n /= p;
                i++;
            }
            if (i > 0) ret[rp++] = p;
        }
        if (n != 1) ret[rp++] = n;
        return Arrays.copyOf(ret, rp);
    }

    public static int[] sieveEratosthenes(int n) {
        if (n <= 32) {
            int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
            for (int i = 0; i < primes.length; i++) {
                if (n < primes[i]) {
                    return Arrays.copyOf(primes, i);
                }
            }
            return primes;
        }

        int u = n + 32;
        double lu = Math.log(u);
        int[] ret = new int[(int) (u / lu + u / lu / lu * 1.5)];
        ret[0] = 2;
        int pos = 1;

        int[] isnp = new int[(n + 1) / 32 / 2 + 1];
        int sup = (n + 1) / 32 / 2 + 1;

        int[] tprimes = {3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
        for (int tp : tprimes) {
            ret[pos++] = tp;
            int[] ptn = new int[tp];
            for (int i = (tp - 3) / 2; i < tp << 5; i += tp) ptn[i >> 5] |= 1 << (i & 31);
            for (int j = 0; j < sup; j += tp) {
                for (int i = 0; i < tp && i + j < sup; i++) {
                    isnp[j + i] |= ptn[i];
                }
            }
        }

        // 3,5,7
        // 2x+3=n
        int[] magic = {
                0, 1, 23, 2, 29, 24, 19, 3, 30, 27, 25, 11, 20, 8, 4, 13, 31, 22, 28, 18, 26, 10, 7, 12, 21,
                17, 9, 6, 16, 5, 15, 14
        };
        int h = n / 2;
        for (int i = 0; i < sup; i++) {
            for (int j = ~isnp[i]; j != 0; j &= j - 1) {
                int pp = i << 5 | magic[(j & -j) * 0x076be629 >>> 27];
                int p = 2 * pp + 3;
                if (p > n) break;
                ret[pos++] = p;
                if ((long) p * p > n) continue;
                for (int q = (p * p - 3) / 2; q <= h; q += p) isnp[q >> 5] |= 1 << q;
            }
        }

        return Arrays.copyOf(ret, pos);
    }


    private static final boolean oj = System.getProperty("ONLINE_JUDGE") != null;

    private static void tr(Object... o) {
        if (!oj) System.out.println(Arrays.deepToString(o));
    }
}