#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "functional"

using namespace std;

//constexpr long long int MOD = 1000000007;
constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-8;

//int N, M, K, H, W, L, R;
long long int N, M, K, H, W, L, R;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> M;
	vector<vector<long long int>>v(N,vector<long long int>(M));
	for (auto &i : v) {
		for (auto &j : i)cin >> j;
	}
	for (int i = 1; i < N; i++) {
		if (v[i][0] < v[i - 1][0]) {
			cout << -1 << endl;
			return 0;
		}
	}
	if (M == 1) {
		for (int i = 1; i < N; i++) {
			if (v[i][0] <= v[i - 1][0]) {
				cout << -1 << endl;
				return 0;
			}
		}
	}
	vector<long long int>num(N);
	vector<long long int>box(M);
	bitset<5000>bs;
	for (int i = N - 1; i > 0; i--) {
		if (v[i][0] != v[i - 1][0])continue;
		bs.flip(i);
		if (v[i] > v[i - 1]) {
			box = v[i - 1];
			int dif = v[i][1] - v[i - 1][1];
			if (dif%v[i - 1][0]) {
				num[i] = -dif / v[i - 1][0];
			}
			else {
				dif /= v[i - 1][0];
				if (dif >= 100000) {
					dif--;
					num[i] = -(dif);
					continue;
				}
				int sz = M;
				for (int j = 0; j < dif; j++) {
					int sum = box[0];
					for (int k = 1; k < sz; k++) {
						sum += box[k];
						box[k] = sum;
						if (sum > MOD) {
							sz = k;
							break;
						}
					}
				}
				if (box < v[i]) {
					num[i] = -dif;
				}
				else num[i] = -(dif - 1);
			}
		}
		else {
			box = v[i];
			int dif = v[i-1][1] - v[i][1];
			if (dif%v[i][0]) {
				num[i] = dif / v[i][0] + 1;
			}
			else {
				dif /= v[i][0];
				if (dif >= 100000) {
					num[i] = dif;
					continue;
				}
				int sz = M;
				for (int j = 0; j < dif; j++) {
					int sum = box[0];
					for (int k = 1; k < sz; k++) {
						sum += box[k];
						box[k] = sum;
						if (sum > MOD) {
							sz = k;
							break;
						}
					}
				}
				if (box <= v[i-1]) {
					num[i] = dif + 1;
				}
				else num[i] = dif;
			}
		}
	}
	long long int ans = 0;
	long long int used = 0;
	for (int i = 1; i < N; i++) {
		if (bs.test(i)) {
			ans += max(0LL, used + num[i]);
			used= max(0LL, used + num[i]);
		}
		else {
			used = 0;
		}
		//cout << ans << endl;
	}
	cout << ans << endl;
}
