#include<bits/stdc++.h>
using namespace std;
int n,t,s[1005][1005],a,b,mx;
int main()
{
    cin>>n>>t;
    while(t--)
    {
        cin>>a>>b;
        s[a][b]=1;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            s[i][j]=s[i][j]-s[i-1][j-1]+s[i-1][j]+s[i][j-1];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int w=0;w<=n-i;w++)
                if(s[i+w-1][j+w-1]+s[i-1][j-1]-s[i-1][j+w-1]-s[i+w-1][j-1]==0)
                    mx=max(mx,w);
    cout<<mx;
}