#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int p[1010][1010][2],n,m,bk[1010][1010],f[1010][1010][3],ma=1,a1,a2;
int main(){
	freopen("bigbrn.in","r",stdin);
	freopen("bigbrn.out","w",stdout);
    scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a1,&a2);
		bk[a1][a2]=1;
	}
	for(int i=1;i<=n;i++){
		if(bk[i][1])p[i][1][0]=1;
		else p[i][1][0]=2;
	    for(int j=2;j<=n;j++){
		    if(bk[i][j]==0)p[i][j][0]=p[i][j-1][0];
			else p[i][j][0]=j+1;
		}
	}
	for(int i=1;i<=n;i++){
		if(bk[i][n]==0)p[i][n][1]=n;
		else p[i][n][1]=n-1;
	    for(int j=n-1;j>=1;j--){
		    if(bk[i][j]==0)p[i][j][1]=p[i][j+1][1];
			else p[i][j][1]=j-1;
		}
	}
	for(int i=1;i<=n;i++){
	    if(bk[1][i]==0)f[1][i][0]=1,f[1][i][1]=p[1][i][0],f[1][i][2]=p[1][i][1];
	    else f[1][i][0]=2,f[1][i][1]=1,f[1][i][2]=n;
	}
	for(int i=2;i<=n;i++){
	    for(int j=1;j<=n;j++){
		    if(bk[i][j]==0){
				f[i][j][0]=f[i-1][j][0];
				f[i][j][1]=max(p[i][j][0],f[i-1][j][1]);
				f[i][j][2]=min(p[i][j][1],f[i-1][j][2]);
			}
			else{
				f[i][j][0]=i+1;
				f[i][j][1]=1;
				f[i][j][2]=n;
			}
			if(bk[i][j]==0)ma=max(ma,min(i-f[i][j][0]+1,f[i][j][2]-f[i][j][1]+1));
		}
	}
	printf("%d",ma);
    return 0;
}