// Arup Guha
// 4/14/2020
// Solution to 2020 USACO March Silver Contest Problem: Social Distancing

import java.util.*;
import java.io.*;

public class socdist {
	
	public static int nCows;
	public static int nIntervals;
	public static pair[] grass;
	
	public static void main(String[] args) throws Exception {
		
		// Read in the array.
		BufferedReader stdin = new BufferedReader(new FileReader("socdist.in"));
		StringTokenizer tok = new StringTokenizer(stdin.readLine());
		
		nCows = Integer.parseInt(tok.nextToken());
		nIntervals = Integer.parseInt(tok.nextToken());
		grass = new pair[nIntervals];
		
		// Read in grass patches and sort.
		for (int i=0; i<nIntervals; i++) {
			tok = new StringTokenizer(stdin.readLine());
			long s = Long.parseLong(tok.nextToken());
			long e = Long.parseLong(tok.nextToken());
			grass[i] = new pair(s, e);
		}
		Arrays.sort(grass);
		
		// Safe for our binary search.
		long low = 1, high = 1000000000000000000L;
		
		// Run binary search.
		while (low < high) {
			
			long mid = (low+high+1)/2; 
			
			// can we space out cows by mid?
			if (canDo(mid))
				low = mid;
			else
				high = mid-1;
		}
		
		// Output to file.
		PrintWriter out = new PrintWriter(new FileWriter("socdist.out"));
		out.println(low);
		out.close();		
		stdin.close();
	}
	
	public static boolean canDo(long gap) {
		
		// Place first cow at beginning of first interval.
		long curPos = grass[0].low;
		int gIdx = 0;
		
		// Try to place each cow.
		for (int i=1; i<nCows; i++) {
			
			// Where we want to place the next cow.
			long nextPos = curPos + gap;
			
			// Get to first piece of grass that isn't past nextPos.
			while (gIdx < nIntervals && grass[gIdx].high < nextPos) gIdx++;
			
			// No more grass left.
			if (gIdx == nIntervals) return false;
			
			// This is where we place cow number i.
			curPos = Math.max(nextPos, grass[gIdx].low);
		}
		
		// If we make it here, we placed all the cows with gap.
		return true;
	}
}

class pair implements Comparable<pair> {
	
	public long low;
	public long high;
	
	public pair(long a, long b) {
		low = a;
		high = b;
	}
	
	public int compareTo(pair other) {
		if (low < other.low) return -1;
		if (low > other.low) return 1;
		return 0;
	}
}