#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
#define rep(i, n) for(int i=0;i<(n);++i)
#define rep1(i, n) for(int i=1;i<=(n);i++)
#define ll long long
using mint = modint998244353;
using P = pair<ll,ll>;
using lb = long double;
using T = tuple<ll, ll, ll>;
#ifdef LOCAL
#  include <debug_print.hpp>
#  define dbg(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#  define dbg(...) (static_cast<void>(0))
#endif

int main()
{
	int n, m;
	cin >> n >> m;
	vector<vector<int>> flg(m, vector<int>(n));
	vector<set<int>> st(m);
	vector<pair<int, int>> card;
	rep(i,n*m){
		int a, b;
		cin >> a >> b;
		--a;--b;
		card.emplace_back(a,b);
		flg[b][a] = true;
		if(!st[b].empty()) continue;
		for(int j=a-4;j<=a;j++){
			bool ok = true;
			for(int k=0;k<5;k++){
				if(j+k>=n) {
					ok = false;
					break;
				}
				if(!flg[b][j+k]) ok = false;
			}
			if(ok){
				for(int k=j;k<j+5;k++){
					st[b].insert(k);
				}
			}
		}
		bool ok = true;
		for(int j=n-4;j<n;j++) if(!flg[b][a]) ok = false;
		if(!flg[b][0]) ok = false;
		if(ok){
			for(int j=n-4;j<n;j++){
				st[b].insert(j);
			}
			st[b].insert(0);
		}
	}
	dbg(st);
	int ans = n*m;
	rep(i,m){
		int tmp = 0;
		int cnt = 0;
		queue<pair<int, int>> hand;
		rep(j,5) hand.emplace(card[j]);
		int now = 5;
		dbg(hand);
		while(now!=n*m){
			while(!hand.empty()){
				auto [a, b] = hand.front();hand.pop();
				if(i==b && st[i].count(a)) cnt++;
				dbg(a, b);
			}
			dbg(cnt, tmp);
			if(cnt==5){
				ans = min(ans, tmp);
				break;
			}
			for(int j=now;j<min(n*m,now+5-cnt);j++){
				hand.emplace(card[j]);
			}
			now += 5 - cnt;
			now = min(now, n*m-1);
			dbg(now);
			tmp++;
		}
	}

	cout << ans << endl;
	return 0;
}