Problem: Takahashi is a magician. He can cast a spell on an integer sequence (a_1,a_2,...,a_M) with M terms, to turn it into another sequence (s_1,s_2,...,s_M), where s_i is the sum of the first i terms in the original sequence.

One day, he received N integer sequences, each with M terms, and named those sequences A_1,A_2,...,A_N. He will try to cast the spell on those sequences so that A_1 < A_2 < ... < A_N will hold, where sequences are compared lexicographically. Let the action of casting the spell on a selected sequence be one cast of the spell. Find the minimum number of casts of the spell he needs to perform in order to achieve his objective.

Here, for two sequences a = (a_1,a_2,...,a_M), b = (b_1,b_2,...,b_M) with M terms each, a < b holds lexicographically if and only if there exists i (1 ≦ i ≦ M) such that a_j = b_j (1 ≦ j < i) and a_i < b_i.

Constraints

* 1 ≦ N ≦ 10^3
* 1 ≦ M ≦ 10^3
* Let the j-th term in A_i be A_{(i,j)}, then 1 ≦ A_{(i,j)} ≦ 10^9.

Input

The input is given from Standard Input in the following format:


N M
A_{(1,1)} A_{(1,2)} … A_{(1,M)}
A_{(2,1)} A_{(2,2)} … A_{(2,M)}
:
A_{(N,1)} A_{(N,2)} … A_{(N,M)}


Output

Print the minimum number of casts of the spell Takahashi needs to perform. If he cannot achieve his objective, print `-1` instead.

Examples

Input

3 3
2 3 1
2 1 2
2 6 3


Output

1


Input

3 3
3 2 10
10 5 4
9 1 9


Output

-1


Input

5 5
2 6 5 6 9
2 6 4 9 10
2 6 8 6 7
2 1 7 3 8
2 1 4 8 3


Output

11

Solution (in JAVA):

Solution:
// package atcoder.other2016.codefestival2016.round2;

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.InputMismatchException;

public class Main {
    private static final long INF = (long) 4e9;

    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int n = in.nextInt();
        int m = in.nextInt();

        long[][] table = in.nextLongTable(n, m);



        long sum = 0;
        long last = 0;
        for (int i = 0; i+1 < n; i++) {
            if (m == 1) {
                if (table[i][0] < table[i+1][0]) {
                    // ok
                } else {
                    sum = -1;
                    break;
                }
                continue;
            }

            int k = -1;
            for (int j = 0; j < m ; j++) {
                if (table[i][j] == table[i+1][j]) {
                } else {
                    k = j;
                    break;
                }
            }

            if (k == -1) {
                // completely same.
                sum += last+1;
                last = last+1;
            } else if (k == 0) {
                // different at first.
                if (table[i][k] < table[i+1][k]) {
                    last = 0;
                } else {
                    // NG
                    sum = -1;
                    break;
                }
            } else {
                // how many func required actually?
                long head = table[i][0];
                long second = head * last + table[i][1];
                if (second < table[i+1][1]) {
                    last = 0;
                    continue;
                }
                long req = (second - table[i+1][1] + head - 1) / head;
                long tos = head * req + table[i+1][1];
                if (second < tos) {
                    sum += req;
                    last = req;
                    continue;
                }

                // operation required: req or req+1 times.
                if (compare(table[i], last, table[i+1], req) == -1) {
                    sum += req;
                    last = req;
                } else {
                    sum += req+1;
                    last = req+1;
                }
            }
        }

        out.println(sum);
        out.flush();
    }

    private static int compare(long[] a, long opA, long[] b, long opB) {
        if (opA == 0) {
            return compare(a, b, opB);
        } else if (opB == 0) {
            return -compare(b, opB, a, opA);
        } else {
            long dec = Math.min(opA, opB);
            return compare(a, opA-dec, b, opB-dec);
        }
    }

    private static int compare(long[] a, long[] b, long opB) {
        int n = b.length;
        long[] tob = b.clone();
        if (opB <= 32) {
            for (int f = 0 ; f < opB ; f++) {
                operate(tob);
            }
            for (int i = 0 ; i < n ; i++) {
                if (a[i] != tob[i]) {
                    return (a[i] < tob[i]) ? -1 : 1;
                }
            }
        } else {
            for (int k = 1 ; k < n ; k++) {
                long sum = 0;
                int d = 0;
                for (int part = k ; part >= 0 ; part--) {
                    long left = opB+d-1;
                    long right = d;
                    long comb = comb(left, right);
                    if (comb >= INF || b[part] >= INF / comb) {
                        sum = INF;
                        break;
                    }
                    sum += b[part] * comb;
                    if (sum >= INF) {
                        sum = INF;
                        break;
                    }
                    d++;
                }
                tob[k] = sum;
                if (a[k] != tob[k]) {
                    return (a[k] < tob[k]) ? -1 : 1;
                }
            }
        }
        return 0;
    }

    static final int MOD = 1000000007;

    static long pow(long a, long x) {
        long res = 1;
        while (x > 0) {
            if (x%2 != 0) {
                res = (res*a)%MOD;
            }
            a = (a*a)%MOD;
            x /= 2;
        }
        return res;
    }


    static long comb(long n, long r) {
        BigInteger up = BigInteger.ONE;
        BigInteger dw = BigInteger.ONE;
        for (int i = 0; i < r ; i++) {
            up = up.multiply(BigInteger.valueOf(n-i));
            dw = dw.multiply(BigInteger.valueOf(i+1));
        }
        BigInteger ret = up.divide(dw);
        if (ret.compareTo(BigInteger.valueOf(INF)) == -1) {
            return ret.longValue();
        }
        return INF;
    }


    private static void operate(long[] a) {
        long psum = a[0];
        for (int i = 1  ; i < a.length ; i++) {
            psum += a[i];
            if (psum >= INF) {
                psum = INF;
            }
            a[i] = psum;
        }
    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        private int[] nextInts(int n) {
            int[] ret = new int[n];
            for (int i = 0; i < n; i++) {
                ret[i] = nextInt();
            }
            return ret;
        }

        private int[][] nextIntTable(int n, int m) {
            int[][] ret = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    ret[i][j] = nextInt();
                }
            }
            return ret;
        }

        private long[] nextLongs(int n) {
            long[] ret = new long[n];
            for (int i = 0; i < n; i++) {
                ret[i] = nextLong();
            }
            return ret;
        }

        private long[][] nextLongTable(int n, int m) {
            long[][] ret = new long[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    ret[i][j] = nextLong();
                }
            }
            return ret;
        }

        private double[] nextDoubles(int n) {
            double[] ret = new double[n];
            for (int i = 0; i < n; i++) {
                ret[i] = nextDouble();
            }
            return ret;
        }

        private int next() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public char nextChar() {
            int c = next();
            while (isSpaceChar(c))
                c = next();
            if ('a' <= c && c <= 'z') {
                return (char) c;
            }
            if ('A' <= c && c <= 'Z') {
                return (char) c;
            }
            throw new InputMismatchException();
        }

        public String nextToken() {
            int c = next();
            while (isSpaceChar(c))
                c = next();
            StringBuilder res = new StringBuilder();
            do {
                res.append((char) c);
                c = next();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public int nextInt() {
            int c = next();
            while (isSpaceChar(c))
                c = next();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = next();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c-'0';
                c = next();
            } while (!isSpaceChar(c));
            return res*sgn;
        }

        public long nextLong() {
            int c = next();
            while (isSpaceChar(c))
                c = next();
            long sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = next();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c-'0';
                c = next();
            } while (!isSpaceChar(c));
            return res*sgn;
        }

        public double nextDouble() {
            return Double.valueOf(nextToken());
        }

        public boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }

    static void debug(Object... o) {
        System.err.println(Arrays.deepToString(o));
    }
}