#include <bits/stdc++.h>
using namespace std;
int n,k,t,a[505],b[505],sum[1005][1005];
vector<int> v;
int dis(int x){
	return lower_bound(v.begin(),v.end(),x)-v.begin();
}
int sub(int x,int y,int x2,int y2){
	return sum[x2][y2]-sum[x][y2]-sum[x2][y]+sum[x][y];
}
bool check(int d){
	int x=0,y,x2=1,y2;
	while(x2++<t){
		while(v[x2]-v[x+1]>=d)x++;
		for(y=0,y2=1;y2<t;y2++){
			while(v[y2]-v[y+1]>=d)y++;
			if(sub(x,y,x2,y2)>=k)return 1;
		}
	}
	return 0;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>k>>n;
	v.push_back(0);
	for(int i=1;i<=n;i++){
		int x,y;
		cin>>x>>y;
		v.push_back(x);
		v.push_back(y);
		a[i]=x,b[i]=y;
	}
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	for(int i=1;i<=n;i++){
		sum[dis(a[i])][dis(b[i])]++;
	}
	t=v.size();
	for(int i=1;i<t;i++){
		for(int j=1;j<t;j++){
			sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
		}
	}
	int l=1,r=1e4;
	while(l<r){
		int mid=l+r>>1;
		if(check(mid))r=mid;
		else l=mid+1;
	}
	cout<<l<<"\n";
	return 0;	
}