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