Задача №1632. Операционные системы
Васин жесткий диск состоит из M секторов. Вася последовательно устанавливал на него различные операционные системы следующим методом: он создавал новый раздел диска из последовательных секторов, начиная с сектора номер ai и до сектора bi включительно, и устанавливал на него очередную систему. При этом, если очередной раздел хотя бы по одному сектору пересекается с каким-то ранее созданным разделом, то ранее созданный раздел «затирается», и операционная система, которая на него была установлена, больше не может быть загружена.
Напишите программу, которая по информации о том, какие разделы на диске создавал Вася, определит, сколько в итоге работоспособных операционных систем установлено и работает в настоящий момент на Васином компьютере.
Формат входных данных
Сначала вводятся натуральное число M — количество секторов на жестком диске (1 ≤ M ≤ 109) и целое число N — количество разделов, которое последовательно создавал Вася (0 ≤ N ≤ 1000).
Далее идут N пар чисел ai и bi, задающих номера начального и конечного секторов раздела
(1 ≤ ai ≤ bi ≤ M).
Формат выходных данных
Выведите одно число — количество работающих операционных систем на Васином компьютере.
Input:
10
3
1 3
4 7
3 4
Output:
1