#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> nm(m, vector<int>(n));
	for (int i = 0; i < n * m; i++) {
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		nm[v][u] = max(i - 4, 0);
	}
	int ans = INT_MAX;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n - 3; j++) {
			int res = 0;
			// cerr<<i<<' '<<j<<endl;
			int k = j;
			do {
				// cerr<<k<<' '<<nm[i][k]<<endl;
				res = max(res, nm[i][k]);
				(++k) %= n;
			} while (k != (j + 5) % n);
			// cerr<<endl;
			ans = min(ans, res);
		}
	}
	cout << ans << endl;
}