#include<cstdio>
#include<algorithm>
#define maxn 1039
using namespace std;
int n,c;
struct JTZ{
int x,y;
bool operator < (const JTZ x) const{
if(this->x == x.x)
return this->y < x.y;
return this->x < x.x;
}
}a[maxn];
int check(int x){
int sum;
for(int i=1;i<=n;i++){
sum=0;
for(int j=1;j<=n;j++)
if( (a[i].x <= a[j].x) && (a[j].x <= (a[i].x+x)) )
if( (a[i].y <= a[j].y) && (a[j].y <= (a[i].y+x)) )
sum++;
if(sum>=c) return 1;
}
return 0;
}
int main(){
scanf("%d%d",&c,&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i].x,&a[i].y);
int l,r,mid;
l=-2,r=9999;
while(l+1<r){
mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid;
}
printf("%d",l+2);
return 0;
}