Задача Операционные системы

Описание

Васин жесткий диск состоит из M секторов. Вася последовательно устанавливал на него различные операционные системы следующим методом: он создавал новый раздел диска из последовательных секторов, начиная с сектора номер ai и до сектора bi включительно, и устанавливал на него очередную систему. При этом если очередной раздел хотя бы по одному сектору пересекается с каким-то ранее созданным разделом, то ранее созданный раздел «затирается», и операционная система, которая на него была установлена, больше не может быть загружена.

Напишите программу, которая по информации о том, какие разделы на диске создавал Вася, определит, сколько в итоге работающих операционных систем установлено и в настоящий момент работает на Васином компьютере.

Формат входных данных

Сначала вводятся натуральное число M — количество секторов на жестком диске (1 ≤ M ≤ 10 ⁹ ) и целое число N — количество разделов, которое последовательно создавал Вася (0 ≤ N ≤ 100 000).

Далее идут N пар чисел ai и bi, задающих номера начального и конечного секторов раздела (1 ≤ ai ≤ bi ≤ M).

Формат выходных данных

Выведите одно число — количество работающих операционных систем на Васином компьютере.