#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e3+5;
int n,m,a[MAXN][MAXN],sum[MAXN][MAXN],ans=0,l,r;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL),cout.tie(NULL);
	memset(a,0,sizeof(a));
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		l=max(l,x),r=max(r,y);
		a[x][y]++;
	}
	for(int i=1;i<=r;i++){
		sum[1][i]=sum[1][i-1]+a[1][i];
	}
	for(int i=2;i<=l;i++){
		sum[i][1]=sum[i-1][1]+a[i][1];
	}
	for(int i=2;i<=l;i++){
		for(int j=2;j<=r;j++){
			sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
		}
	}
	if(n==1){
		cout<<1;
	} else {
		bool flag=true;
		for(int len=2;len<=min(l,r);len++){
			for(int i=1;i+len-1<=r;i++){
				for(int j=1;j+len-1<=l;j++){
					int x=j,y=i;
					ans=sum[j+len-1][i+len-1]+sum[x-1][y-1]-sum[j+len-1][y-1]-sum[x-1][i+len-1];
					if(ans>=n){
						ans=len;
						flag=false;
						break;
					}
				}
				if(flag==false){
					break;
				}
			}
			if(flag==false){
				break;
			}
		}
		cout<<ans;
	}
	return 0;
}