#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e3 + 5;

struct Point{
    int x, y;
}points[N >> 1];
int sum[N][N], temp[N], cnt;
int c, n, length;

bool check(int size)
{
    for (int x1 = 1, x2 = 1; x2 <= length; x2++)
    {
        while (temp[x2] - temp[x1] + 1 > size) x1++;
        for (int y1 = 1, y2 = 1; y2 <= length; y2++)
        {
            while (temp[y2] - temp[y1] + 1> size) y1++;
            if (sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1] >= c) return true;
        }
    }
    return false;
}

int main()
{
    scanf("%d%d", &c, &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &points[i].x, &points[i].y);
        temp[++cnt] = points[i].x;
        temp[++cnt] = points[i].y;
    } 

    //离散化 
    sort(temp+1, temp+1+cnt);
    length = unique(temp+1, temp+1+cnt) - (temp+1);
    for (int i = 1; i <= n; i++)
    {
        int x = lower_bound(temp+1, temp+1+length, points[i].x) - (temp+1) + 1;
        int y = lower_bound(temp+1, temp+1+length, points[i].y) - (temp+1) + 1;
        sum[x][y]++;
    }

    //前缀和 
    for (int i = 1; i <= length; i++)
    {
        for (int j = 1; j <= length; j++)
        {
            sum[i][j] += sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
        }
    }

    //二分答案
    int l = 1, r = 10000, res = 0;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (check(mid)) 
        {
            res = mid;
            r = mid - 1;
        }   
        else l = mid + 1; 
    } 
    printf("%d", res);
    return 0;
}