#include<cstdio>
#include<cstring>
#include<algorithm>
#define ri register int
using namespace std;
const int N=510;
int l,r,mid,ans;
int C,n,len,b[N<<1],sum[N<<1][N<<1];
struct node{int x,y;}a[N<<1];
inline int get(int x){return lower_bound(b+1,b+len+1,x)-b;}
bool check(int k)
{
	//这两个循环用的都是b数组，就不会出现把横边算成竖边或者反过来算吗？
	for(ri x1=1,x2=1;x2<=len;x2++)
	{
		while(b[x2]-b[x1]+1>k) x1++;
		for(ri y1=1,y2=1;y2<=len;y2++)
		{
			while(b[y2]-b[y1]+1>k) y1++;
			if(sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]>=C) return true;
		} 
	}
	return false;
}
int main()
{
	scanf("%d %d",&C,&n);
	for(ri i=1;i<=n;i++)
	{
		scanf("%d %d",&a[i].x,&a[i].y);
		b[i]=a[i].x,b[n+i]=a[i].y;
	}
	a[0].x=a[0].y=1;
	sort(b+1,b+(n<<1)+1);
	len=unique(b+1,b+(n<<1)+1)-b-1;
	for(ri i=1;i<=n;i++)
	{
		int x=get(a[i].x),y=get(a[i].y);
		sum[x][y]++;
	}
	for(ri i=1;i<=len;i++)
		for(ri j=1;j<=len;j++)
			sum[i][j]=sum[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
	l=1,r=10000,mid=(l+r)>>1;
	while(l<=r)
	{
		if(check(mid)) ans=mid,r=mid-1;
		else l=mid+1;
		mid=(l+r)>>1;
	}
	printf("%d",ans);
	return 0;
}