#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
int n, m, head[100005], nxt[200005], to[200005], w[200005], ccnt, minn = 0x3f3f3f3f, dis[200005];
vector<pair<int, int>> son[100005];
inline void add(int p, int q, int ww) {
//	cout << p << " " << q << " " << ww << "\n";
	nxt[++ccnt] = head[p];
	to[ccnt] = q;
	w[ccnt] = ww;
	head[p] = ccnt;
}
inline void dfs(int p) {
	for (int &i = head[p]; i; i = nxt[i]) {
		if (dis[to[i]]) {
			minn = min(minn, dis[p] - dis[to[i]] + w[i]);
		} else {
			dis[to[i]] = dis[p] + w[i];
			dfs(to[i]);
		}
	}
	dis[p] = 0;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	int p;
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> p;
			son[j].push_back(make_pair(p, i));
		}
	}
	for (int i = 1; i <= n; i++) {
		sort(son[i].begin(), son[i].end());
		for (int j = 1; j <= m - 1; j++) {
			if (son[i][j - 1].first && son[i][j].first) {
				add(son[i][j - 1].second, son[i][j].second, son[i][j].first - son[i][j - 1].first);
			}
		}
	}
	dis[1] = 1;
	dfs(1);
	if (minn == 0x3f3f3f3f) {
		cout << -1;
	} else {
		cout << minn;
	}
}