Ремонт проспекта

В городе есть длинный проспект от отметки 0 до L (всё измеряется вдоль одной линии).

Дорожные бригады уже готовы: каждая бригада умеет отремонтировать ровно один участок проспекта — от l до r (где l < r). Участки можно выбирать в любом порядке, они могут пересекаться.

Мэр хочет, чтобы после выбора бригад весь проспект от 0 до L был покрыт ремонтом (то есть каждая точка на отрезке [0; L] должна принадлежать хотя бы одному выбранному участку). Бригад хочется выделить как можно меньше.

Найдите минимальное число участков, которыми можно покрыть весь проспект. Если это невозможно — выведите -1.

Формат ввода

В первой строке даны два целых числа L и n — длина проспекта и число предложенных участков.

В следующих n строках даны пары целых чисел lᵢ rᵢ — границы i-го участка.

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

Выведите одно целое число — минимальное количество участков, достаточное для покрытия [0; L], или -1, если покрытия добиться нельзя.

Ограничения

• 1 ≤ L ≤ 1000
• 1 ≤ n ≤ 200000
• 0 ≤ lᵢ < rᵢ ≤ L

Пример

Ввод:

10 4
0 4
3 8
7 10
1 6

Вывод:

3

Заметка-переформулировка: нам нужно покрыть [0; L] минимальным числом отрезков. Если мы уже покрыли всё до точки cur, то следующий выбранный отрезок обязан начинаться в l <= cur, иначе между ними будет «дыра».

Ключевое наблюдение: среди всех отрезков, которые начинаются не позже cur, всегда выгодно взять тот, у которого правая граница максимальна. Это жадный шаг: он не ухудшает ответ, потому что любой другой выбор продвинет нас не дальше, а значит может только увеличить число отрезков.

План решения:

• Считай все отрезки (l, r).
• Отсортируй их по l (если равны — по r не важно, но удобно).
• Держи:
• cur — текущая покрытая граница (сначала 0),
• указатель i по отсортированному списку,
• best — самый дальний r среди всех отрезков с l <= cur.
• Пока cur < L:
• просмотром увеличивай i, пока l[i] <= cur, и обновляй best = max(best, r[i]).
• если после этого best <= cur, значит ни один отрезок не может продолжить покрытие → ответ -1.
• иначе «берём» один отрезок, делаем cur = best, увеличиваем счётчик.

Подсказка-формула: обновление дальности — best = max(best, r).

Сложность: сортировка O(n log n), проход указателем O(n), память O(n).

Частая ошибка: выбирать отрезок с минимальным l или просто первый подходящий. Нужно именно максимизировать r среди всех с l <= cur, иначе можно получить лишние отрезки или застрять.