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 CPP):

Solution:
// #pragma GCC target("avx2")  // CPU 処理並列化
// #pragma GCC optimize("O3")  // CPU 処理並列化
// #pragma GCC optimize("unroll-loops")  // 条件処理の呼び出しを減らす
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<numeric>
using namespace std;
const long long mod=1000010007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3121000;
long long fact[C_SIZE];
long long finv[C_SIZE];
long long inv[C_SIZE];
long long Comb(int a,int b){
 	if(a<b||b<0)return 0;
 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
}
void init_C(int n){
	fact[0]=finv[0]=inv[1]=1;
	for(int i=2;i<n;i++){
		inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	}
	for(int i=1;i<n;i++){
		fact[i]=fact[i-1]*i%mod;
		finv[i]=finv[i-1]*inv[i]%mod;
	}
}
long long pw(long long a,long long b){
	if(a<0LL)return 0;
	if(b<0LL)return 0;
	long long ret=1;
	while(b){
		if(b%2)ret=ret*a%mod;
		a=a*a%mod;
		b/=2;
	}
	return ret;
}
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
double ABS(double a){return max(a,-a);}
int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
// ここから編集しろ
long long p[1100][1100];
long long t[1100];
int main(){

	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++){
		for(int j=0;j<b;j++)scanf("%lld",&p[i][j]);
	}
	for(int i=0;i<a-1;i++)if(p[i][0]>p[i+1][0]){
		printf("-1\n");
		return 0;
	}
	if(b==1){
		for(int i=0;i<a-1;i++)if(p[i][0]>=p[i+1][0]){
			printf("-1\n");
			return 0;
		}
		printf("0\n");	return 0;
	}
	long long ret=0;
	long long cur=0;
	for(int i=1;i<a;i++){
		if(p[i-1][0]!=p[i][0]){cur=0;continue;}
		long long now=p[i-1][0]*cur+p[i-1][1];
		if(p[i][1]>now){
			cur=0;continue;
		}
		long long req=(now-p[i][1]+p[i][0]-1)/p[i][0];

		if(p[i][1]+p[i][0]*req>now){
			cur=req;
			ret+=req;
			continue;
		}
		bool ok=false;
		long long P=ABS(cur-req);
		if(P>mod)return 1;
		if(P==0){

			for(int j=0;j<b;j++){
				if(p[i-1][j]<p[i][j]){ok=true;break;}
				if(p[i-1][j]>p[i][j]){break;}
			}

		}else{
			t[0]=1;
			for(int j=1;j<b;j++){
				if(t[j-1]==mod){t[j]=mod;continue;}
				t[j]=t[j-1]*(P-1+j)/j;
				if(t[j]>mod){
					t[j]=mod;
				}
			}
			for(int j=2;j<b;j++){
				if(req<cur){	
					long long tmp=p[i][j];
					for(int k=j;k>=0;k--){
						tmp-=t[k]*p[i-1][j-k];
						if(tmp<0)break;
					}
					if(tmp<0){
						break;
					}
					if(tmp>0){
						ok=true;break;
					}
				}else{
					long long tmp=p[i-1][j];
					for(int k=j;k>=0;k--){
						tmp-=t[k]*p[i][j-k];
						if(tmp<0)break;
					}
					if(tmp<0){
						ok=true;break;
					}
					if(tmp>0){
						break;
					}
				}
			}			
		}

		if(!ok){
			req++;
		}
		ret+=req;
		cur=req;
	//	printf("%lld %lld\n",ret,cur);
	}
	printf("%lld\n",ret);
}