/*
本题求最小边长，使得最小边长围成的正方形能容纳指定数量的三叶草，首先三叶草的数量不多，但是数据范围很大， 因此第一步可以进行离散化。然后为了方便知道某一个矩形中的三叶草数量，可以采用前缀和的思想，然后要求边长的最小值，求最小值启发我们用二分来做。因此每次二分一个边长 mid，然后枚举图中所有边长为 mid 的正方形，如果存在一个正方形中的三叶草数量满足要求，可以尝试缩小边长，二分左区间。否则二分右区间。枚举过程中用二维前缀和直接线性求三叶草数量即可。
*/

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
struct node
{
	int x,y;
}nodes[10010];
int n, m, k;
int s[N][N];
int cnt = 1;
int len;
int nums[N];
int find(int x) //离散化
{
    int l = 1, r = cnt-1;
    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        if(nums[mid] <= x) l = mid;
        else r = mid - 1;
    }
    return r;
}
bool check(int mid) //判断边长为 mid 是否能包含 m  个三叶草
{
    for(int x1 = 1, x2 = 1; x2 < cnt; x2++) //枚举横坐标
    {
        while(nums[x2] + 1 - nums[x1] > mid) x1++;
        for(int y1 = 1, y2 = 1; y2 < cnt; y2++) //枚举纵坐标
        {
            while(nums[y2] + 1 - nums[y1] > mid) y1++;
            if(s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] >= m)
                return true;
        }
    }

    return false;
}

int main()
{
    scanf("%d%d", &m, &k);
    for(int i = 0; i < k; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        n = max(n, x), n = max(n, y); //记录边界
        nums[++len] = x;
        nums[++len] = y;
        nodes[i] = (node){x, y}; //存储所有的点
    }
    //坐标离散化
   	sort(nums + 1, nums + len + 1);
   	
   	for(int i = 1; i <= len ; i++)
   		if(nums[i] != nums[i-1])
   			nums[cnt++] = nums[i];

    //标记所有位置上的三叶草数量
    for(int i = 0; i < k; i++)
    {
        int x = find(nodes[i].x), y = find(nodes[i].y);
        s[x][y]++;
    }
    //初始化前缀和
    for(int i = 1; i < cnt; i++)
        for(int j = 1; j < cnt; j++)
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
    //二分
    int l = 1, r = n;
    int ans;
    while(l <= r)
    {
        int mid = l + r >> 1;
        if(check(mid)) 
        {
        	ans = mid;
        	r = mid - 1;
        }
        else l = mid + 1;
    }
    printf("%d\n", ans);
    return 0;
}