import java.util.*;
import java.io.*;
public class socdist{
    public static boolean isValid(int dist){
        int index = 0;
        int cur = is[index].u;//cow position
        for(int i = 1;i<n;i++){
            cur+=dist;
            while(cur>is[index].v){
                index++;
                if(index>=is.length) return false;
            }
            if(cur<is[index].u) cur = is[index].u;
        }
        return true;
    }
    public static int dfs(int low,int high){
        while(high-low!=1){
            int mid = (high+low)/2;
            if(isValid(mid)) low = mid;
            else high = mid;
        }
        return low;
    }
    static int n;
    static interval[] is;//intervals
    public static void main(String[] args)throws IOException{
        BufferedReader bf = new BufferedReader(new FileReader("socdist.in"));
        PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("socdist.out")));
        String[] items = bf.readLine().split(" ");
        n = Integer.parseInt(items[0]);
        int amount = Integer.parseInt(items[1]);
        is = new interval[amount];
        for(int i = 0;i<amount;i++){
            items = bf.readLine().split(" ");
            int start = Integer.parseInt(items[0]);
            int end = Integer.parseInt(items[1]);
            is[i] = new interval(start,end);
        }
        Arrays.sort(is);
        out.println(dfs(1,is[amount-1].v));
        bf.close();
        out.close();
    }
}
class interval implements Comparable<interval>{
    public int u,v;
    public interval(int a,int b){
        this.u = a;
        this.v = b;
    }

    @Override
    public int compareTo(interval o) {
        // TODO Auto-generated method stub
        return Integer.compare(this.u,o.u);
    }
}