// Arup Guha
// 11/5/2016
// Solution to SER 2016 Division I Problem H: Paint

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

public class paint {

	public static void main(String[] args) throws Exception {

		// Read in potentially big data.
		BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tok = new StringTokenizer(stdin.readLine());
		long n = Long.parseLong(tok.nextToken());
		int len = Integer.parseInt(tok.nextToken());
		pair[] arr = new pair[len];
		for (int i=0; i<len; i++) {
			tok = new StringTokenizer(stdin.readLine());
			long a = Long.parseLong(tok.nextToken());
			long b = Long.parseLong(tok.nextToken());
			arr[i] = new pair(a,b);
		}
		
		// Sort it.
		Arrays.sort(arr);
		
		// Set up our tree map for intervals.
		TreeMap<Long,Long> map = new TreeMap<Long,Long>();
		long best = arr[0].range;
		map.put(arr[0].high, best);

		// Go through it, in order.
		for (int i=1; i<len; i++) {

			// Get the best answer lower than where this slat starts.
			Long prev = map.lowerKey(arr[i].low);

			// We can only place this by itself, so do it.
			if (prev == null) {
				long cur = arr[i].range;
				
				// Update if this is better than anything before.
				if (cur > best) {
					best = cur;
					map.put(arr[i].high, best);
				}
			}

			// We can add this slat to a previous solution.
			else {

				// Here is the best answer we get this way.
				long last = map.get(prev);
				long cur = arr[i].range + last;
				
				// Update if it's better.
				if (cur > best) {
					best = cur;
					map.put(arr[i].high, best);
				}
			}
		}

		// This is the answer that we want, the flip answer...
		System.out.println(n-best);
	}
}

class pair implements Comparable<pair> {

	public long low;
	public long high;
	public long range;

	public pair(long a, long b) {
		low = a;
		high = b;
		range = high-low+1;
	}

	public int compareTo(pair other) {
		if (this.high < other.high) return -1;
		if (this.high > other.high) return 1;
		if (this.low < other.low) return -1;
		if (this.low > other.low) return 1;
		return 0;
	}
}