#include<iostream>
#include<cstdio>
using namespace std;
int x,y,ans=0,n,t,farm[1001][10001],h[1001][1001],l[1001][1001],r[1001][1001];
int main(){
	freopen("bigbrn.in","r",stdin);
	freopen("bigbrn.out","w",stdout);
	cin>>n>>t;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			farm[i][j]=1;
			h[i][j]=1;
		    l[i][j]=0;
		    r[i][j]=0;
		}
	for(int i=1;i<=t;i++){
		cin>>x>>y;
		farm[x][y]=0;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			int i2=i;
			int j2=j;
			int j3=j;
			while(farm[i][j2]==1){
				l[i][j]=j2;
				j2--;
			}
			while(farm[i][j3]==1){
				r[i][j]=j3;
				j3++;
			}
			if(farm[i2-1][j]==1){
				h[i][j]+=h[i2-1][j];
				l[i][j]=max(l[i][j],l[i2-1][j]);
				r[i][j]=min(r[i][j],r[i2-1][j]);
			}
			ans=max(ans,min(r[i][j]-l[i][j]+1,h[i][j]));
		}
	cout<<ans;
	return 0;
}