#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;
}