Фонари для парадного проспекта

В городе готовят ночной парад по прямому проспекту. Маршрут идёт от точки 0 до точки L.

Подрядчики привезли фонари. Каждый фонарь освещает отрезок проспекта [l_i, r_i] (включая концы). Если поставить несколько фонарей, то освещённой считается любая точка, попавшая хотя бы в один из отрезков.

Нужно осветить весь маршрут [0, L] минимальным числом фонарей. Если это невозможно — сообщите об этом.

Формат ввода

В первой строке записаны два целых числа L и n — длина маршрута и число фонарей. В следующих n строках записаны по два целых числа l_i и r_i — границы освещения i-го фонаря.

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

Выведите одно целое число — минимальное количество фонарей, которыми можно полностью осветить [0, L]. Если это невозможно, выведите -1.

Ограничения

• 1 ≤ n ≤ 200000
• 1 ≤ L ≤ 10^9
• -10^9 ≤ l_i < r_i ≤ 10^9
• Время: 1.5 секунды, память: 256 МБ

Пример

Ввод:

10 4
0 3
2 10
0 10
8 9

Вывод:

1

(Достаточно одного фонаря, который освещает весь отрезок [0, 10].)

Ключевое наблюдение: если мы уже осветили всё до точки cur, то следующий фонарь имеет смысл выбирать только среди тех, у кого l_i <= cur (они «подхватывают» освещённый край). Среди них оптимально взять тот, у которого r_i максимален — он даёт самый большой прогресс, и это не может ухудшить ответ: любой другой выбор оставит нас не дальше и потребует не меньше фонарей.

Почему жадность работает: мы строим покрытие слева направо. На каждом шаге важно максимально увеличить правую границу освещения, не создавая разрывов. Если в некоторый момент можно выбрать несколько фонарей, то выбор с меньшим r никогда не поможет покрыть больше, чем выбор с максимальным r, а значит может только увеличить число шагов.

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

• Считайте все отрезки, отсортируйте по l_i (при равных l порядок не важен).
• Держите cur = 0 — текущая правая граница уже покрытого.
• Идём указателем по отсортированным отрезкам и среди всех с l_i <= cur обновляем best_reach = max(best_reach, r_i).
• Когда отрезки с l_i <= cur закончились:
• если best_reach <= cur, дальше не продвинуться → ответ -1;
• иначе «выбираем» один фонарь, делаем cur = best_reach, увеличиваем счётчик.
• Повторяем, пока cur >= L.

Мини-сниппет идеи обновления: while i<n and seg[i].l<=cur: best=max(best, seg[i].r).

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

Частая ошибка: проверять достижение как cur == L вместо cur >= L (отрезки могут выходить за L), и забывать случай разрыва, когда best_reach не сдвинулся (тогда сразу -1).