#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
struct node {int x,y;} a[1005];
int C,n,L,R,mid,b[1005],o,i;
int cmp(node i,node j) {return i.x<j.x;}
int CMP(int i,int j) {return i<j;}
bool WORK(int l,int r)
{
if (r-l+1<C) return false; o=0;
for (int i=l; i<=r; i++) b[++o]=a[i].y;
sort(b+1,b+o+1,CMP);
for (int i=C; i<=o; i++)
if (b[i]-b[i-C+1]<=mid) return true;
return false;
}
bool OK(int x)
{
int l=1;
for (int i=1; i<=n; i++)
{
if (a[i].x-a[l].x>x)
{
if (WORK(l,i-1)) return true;
while (a[i].x-a[l].x>x) l++;
}
}
if (WORK(l,n)) return true;
return false;
}
int main()
{
scanf("%d%d",&C,&n);
for (i=1; i<=n; i++)
scanf("%d%d",&a[i].x,&a[i].y);
sort(a+1,a+n+1,cmp);
L=0; R=10000; mid=(L+R)/2;
while (L<=R)
{
if (OK(mid)) {R=mid-1; mid=(L+R)/2;} else
{
L=mid+1;
mid=(L+R)/2;
}
}
cout<<L+1;
return 0;
}