#include<bits/stdc++.h>
const int maxn=1001;
inline const void read(int &a)
{
	a=0;
	char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')
	{
		a=(a<<1)+(a<<3)+c-'0';
		c=getchar();
	}
}
struct point
{
	int x,y;
}p[maxn];
int c,n,ans=INT_MAX;
void get(int i,int step,int up,int down,int left,int right)
{
	if(step==c)
	{
		ans=std::min(ans,std::max(up-down,right-left));
		return;
	}
	if(c-step>n-i)return ;
	get(i+1,step,up,down,left,right);
	get(i+1,step+1,std::max(up,p[i].y),std::min(down,p[i].y),
				   std::min(left,p[i].x),std::max(right,p[i].x));
}
int main()
{
	read(c);read(n);
	for(int i=1;i<=n;i++){read(p[i].x);read(p[i].y);}
	get(1,0,1,10001,10001,1);
	std::cout<<ans+1;
	return 0;
}