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:
#include <bits/stdc++.h>
using namespace std;

using ll=long long;
#define int ll

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif

template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;

template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u>& p){
	return os<<"{"<<p.a<<","<<p.b<<"}";
}

template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
	os<<"{";
	for(auto e:v)os<<e<<",";
	return os<<"}";
}

#define mp make_pair
#define mt make_tuple
#define one(x) memset(x,-1,sizeof(x))
#define zero(x) memset(x,0,sizeof(x))
#ifdef LOCAL
void dmpr(ostream&os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
	os<<t<<" ";
	dmpr(os,args...);
}
#define dmp2(...) dmpr(cerr,"Line:",__LINE__,##__VA_ARGS__)
#else
#define dmp2(...) void(0)
#endif

using uint=unsigned;
using ull=unsigned long long;

template<class t,size_t n>
ostream& operator<<(ostream&os,const array<t,n>&a){
	return os<<vc<t>(all(a));
}

template<int i,class T>
void print_tuple(ostream&,const T&){
}

template<int i,class T,class H,class ...Args>
void print_tuple(ostream&os,const T&t){
	if(i)os<<",";
	os<<get<i>(t);
	print_tuple<i+1,T,Args...>(os,t);
}

template<class ...Args>
ostream& operator<<(ostream&os,const tuple<Args...>&t){
	os<<"{";
	print_tuple<0,tuple<Args...>,Args...>(os,t);
	return os<<"}";
}

void print(ll x,int suc=1){
	cout<<x;
	if(suc==1)
		cout<<"\n";
	if(suc==2)
		cout<<" ";
}

ll read(){
	ll i;
	cin>>i;
	return i;
}

vi readvi(int n,int off=0){
	vi v(n);
	rep(i,n)v[i]=read()+off;
	return v;
}

template<class T>
void print(const vector<T>&v,int suc=1){
	rep(i,v.size())
		print(v[i],i==int(v.size())-1?suc:2);
}

string readString(){
	string s;
	cin>>s;
	return s;
}

template<class T>
T sq(const T& t){
	return t*t;
}

//#define CAPITAL
void yes(bool ex=true){
	#ifdef CAPITAL
	cout<<"YES"<<endl;
	#else
	cout<<"Yes"<<endl;
	#endif
	if(ex)exit(0);
}
void no(bool ex=true){
	#ifdef CAPITAL
	cout<<"NO"<<endl;
	#else
	cout<<"No"<<endl;
	#endif
	if(ex)exit(0);
}
void possible(bool ex=true){
	#ifdef CAPITAL
	cout<<"POSSIBLE"<<endl;
	#else
	cout<<"Possible"<<endl;
	#endif
	if(ex)exit(0);
}
void impossible(bool ex=true){
	#ifdef CAPITAL
	cout<<"IMPOSSIBLE"<<endl;
	#else
	cout<<"Impossible"<<endl;
	#endif
	if(ex)exit(0);
}

constexpr ll ten(int n){
	return n==0?1:ten(n-1)*10;
}

const ll infLL=LLONG_MAX/3;

#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif

int topbit(signed t){
	return t==0?-1:31-__builtin_clz(t);
}
int topbit(ll t){
	return t==0?-1:63-__builtin_clzll(t);
}
int botbit(signed a){
	return a==0?32:__builtin_ctz(a);
}
int botbit(ll a){
	return a==0?64:__builtin_ctzll(a);
}
int popcount(signed t){
	return __builtin_popcount(t);
}
int popcount(ll t){
	return __builtin_popcountll(t);
}
bool ispow2(int i){
	return i&&(i&-i)==i;
}
int mask(int i){
	return (int(1)<<i)-1;
}

bool inc(int a,int b,int c){
	return a<=b&&b<=c;
}

template<class t> void mkuni(vc<t>&v){
	sort(all(v));
	v.erase(unique(all(v)),v.ed);
}

ll rand_int(ll l, ll r) { //[l, r]
	#ifdef LOCAL
	static mt19937_64 gen;
	#else
    static random_device rd;
    static mt19937_64 gen(rd());
    #endif
    return uniform_int_distribution<ll>(l, r)(gen);
}

template<class t>
int lwb(const vc<t>&v,const t&a){
	return lower_bound(all(v),a)-v.bg;
}

void imp(){
	cout<<-1<<endl;
	exit(0);
}

const int L=30;
const int V=2*ten(9);

int cdiv(int a,int b){
	if(a<0)return a/b;
	else return (a+b-1)/b;
}

vi adv(vi a,int k){
	if(k>=L){
		int s=L+1;
		vi buf(s);
		{
			int cur=1;
			rep(i,s){
				buf[i]=cur;
				cur*=k+i;
				cur/=i+1;
				chmin(cur,V);
			}
		}
		dmp2(a,k);
		per(i,a.size()){
			rng(j,1,min({i,L})+1){
				a[i]=min(a[i]+a[i-j]*buf[j],V);
			}
		}
		dmp(a);
	}else{
		rep(_,k){
			rng(i,1,a.size())
				a[i]=min(a[i-1]+a[i],V);
		}
	}
	return a;
}

int sub(vi a,vi b,int x){
	if(a[0]!=b[0]){
		if(a[0]>b[0])imp();
		return 0;
	}
	int n=a.size();
	if(n==1)imp();
	int c=a[0]*x+a[1];
	int y=max(cdiv(c-b[1],b[0]),int(0));
	int d=b[0]*y+b[1];
	if(c<d)return y;
	assert(c==d);
	
	dmp2(a,b,x,y);
	
	if(x<y){
		if(a>=adv(b,y-x))y++;
	}else{
		if(adv(a,x-y)>=b)y++;
	}
	
	dmp(y);
	return y;
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	
	int n,m;cin>>n>>m;
	int ans=0;
	
	vi a=readvi(m);
	int pre=0;
	rep(_,n-1){
		vi b=readvi(m);
		ans+=(pre=sub(a,b,pre));
		a=b;
		dmp(pre);
	}
	
	cout<<ans<<endl;
}