open Scanf
open Printf

let pair a b = a, b

let rec scan_list = function
  | 0 -> []
  | n -> scanf "%d %d\n" (fun a b -> (a,b) :: scan_list (n-1))

let rec hist arr = function
  | [] -> arr
  | (a,b) :: xs -> for i = a to (b-1) do
      arr.(i-1) <- arr.(i-1) + 1
    done;
    hist arr xs

let max_i arr = let n = ref 0 in
  for i = 1 to Array.length arr - 1 do
    if arr.(!n) < arr.(i) then n := i
  done;
  (!n, arr.(!n))

let target n lst = let costs = Array.make (n-1) 0 in 
  max_i (hist costs lst)

let rec remove i ys = function
  | [] -> ys
  | (a, b) :: xs -> if a <= i && i < b
    then remove i ys xs
    else remove i ((a,b)::ys) xs

let rec f ans n = function
  | [] -> ans
  | lst -> let (i, _) = target n lst in f (ans + 1) n (remove (i+1) [] lst)

let () = let n,m = scanf "%d %d\n" pair in
  let lst = scan_list m in
  printf "%d\n" (f 0 n lst)