import java.util.*;
import java.util.concurrent.CancellationException;
import java.util.stream.Collectors;

/**
 * @program: 算法题
 * @author: 上杉
 * @create: 2021-05-03 14:45
 **/
public class Main {
    static int C;
    static int N;
    static int count;
    static int[][] sum ;
    static List<Integer> mp;
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        C = input.nextInt();N = input.nextInt();
        Gav[] gavs = new Gav[N];
        mp = new ArrayList<>();
        mp.add(0);
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < N; i++){
            int x = input.nextInt();
            int y = input.nextInt();
            gavs[i] = new Gav(x,y);
            set.add(x);
            set.add(y);
        }
        mp.addAll(set);
        Collections.sort(mp);
        sum = new int[mp.size()][mp.size()];
        for (int i = 0; i < N; i++) {
            int mx = get(gavs[i].x);
            int my = get(gavs[i].y);
            sum[mx][my]++;
        }
        for (int i = 1; i < mp.size() ; i++) {
            for (int j = 1; j <mp.size() ; j++) {
                sum[i][j] += sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
            }
        }
        int l = 1;
        int r = 10000;
        while (l < r){
            int mid = (l + r) >> 1;
            if(check(mid)){
                r = mid;
            }else {
                l = mid + 1;
            }
        }
        System.out.println(r);

    }

    private static boolean check(int mid) {
        for (int x1 = 0 ,x2 = 1; x2 < mp.size(); x2++) {
            while (mp.get(x2) - mp.get(x1 + 1) + 1 > mid) x1++;
            for (int y1 = 0,y2 = 1; y2 < mp.size() ; y2++) {
                while (mp.get(y2) - mp.get(y1 + 1) + 1 > mid) y1++;
                if(sum[x2][y2] - sum[x1][y2] - sum[x2][y1] + sum[x1][y1] >= C)return true;
            }
        }
        return false;
    }

    private static int get(int x) {
        return Collections.binarySearch(mp,x);
    }

    static class Gav{
        int x;
        int y;

        public Gav(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}