/*
1.因为现在要求包含 n 棵草的最小正方形
直接求比较麻烦 我们可以直接从答案入手
因为答案有范围可以二分枚举答案
2.那么我们现在就要如何快速求出一个矩阵的草有多少个
联想到前缀和可以构造二维前缀和有多少个草这个点的数值就是多少
3.我们可以直接从点开始枚举 
//因为点分布的比较离散直接扫描10000*10000的矩阵比较慢
//但是点的数量才1000*1000直接离散化成一堆连续的点比较快 
因为x,y被放在一起 
*/ 
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int,int> PII;
const int maxn = 1010;
int n,C;
PII points[maxn];
vector<int> numbers;
int sum[maxn][maxn];
int get(int x){//查找x在numbers中的位置
    int l = 0,r = numbers.size() - 1;
    while(l < r){
        int mid = l + r >> 1;
        if(numbers[mid] >= x)   r = mid;
        else    l = mid + 1;
    }
    return r;
}
bool check(int len){//判断是否满足条件
    for(int x1 = 0,x2 = 1;x2 < numbers.size();x2++){
        //number存的是离散化之前的的坐标 虽然有的点是y 但是对于x这一行里前缀和为0里并不包括所以不影响 
        while(numbers[x2] - numbers[x1 + 1] + 1 > len)  x1++;//因为这是二分查找所以判断时只要求是否存在小于len的长度大于c 的草 
        for(int y1 = 0,y2 = 1;y2 < numbers.size();y2++){
            while(numbers[y2] - numbers[y1 + 1] + 1 > len)  y1++;
            if(sum[x2][y2] - sum[x1][y2] - sum[x2][y1] + sum[x1][y1] >= C)  return true;
        }
    }
    return false;
}
// 首先解释一下为甚可以将x, y放入统一个离散化数组里
// 因为离散化只是要求相对位置比如说 排序后的离散化数组为 y1, x2, y2 y3 即使中间插入x相对y与y之间的相对大小还是不变 ；
//所以只要一个离散化数组 
int main(){
    cin>>C>>n;
    numbers.push_back(0);//哨兵
    for(int i = 0;i < n;i++){
        int x,y;
        cin>>x>>y;
        points[i] = {x,y};
        numbers.push_back(x);
        numbers.push_back(y);
    }

    sort(numbers.begin(),numbers.end());//排序 

    numbers.erase(unique(numbers.begin(),numbers.end()),numbers.end());//离散化
    //解释一下上面那个unique函数就是将不重复的数移到前面 --- 比如1223346 -- unique之后就是1234646然后返回第一个重复数得下标 
    //再用number.end() 一直删除
    //因为同一个数值不必同样统计 
    for(int i = 0;i < n;i++){
        int x = get(points[i].first),y = get(points[i].second);//查找这个点离散化位置 用离散化位置建图 
        sum[x][y] ++;  //用sun 
    }
    for(int i = 1;i < numbers.size();i++)
        for(int j = 1;j < numbers.size();j++)
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];//求前缀和
    int l = 1,r = 10000;
    while(l < r){//二分len
        int mid = l + r >> 1;
        if(check(mid))  r = mid;
        else    l = mid + 1;
    }
    cout<<r<<endl;
    return 0;
}