Задача #708

(Д. Статный) Аэропорту необходимо оптимизировать расписание вылетов аэропланов. Для этого они получили список всех полетов с указанием времени вылета и времени прилета. Известно, что в небе одновременно может находиться только один аэроплан, поэтому необходимо составить наиболее оптимальное расписание, чтобы обеспечить максимальное количество вылетов. Если время прибытия одного рейса совпадает со временем вылета другого, то вылет может быть осуществлен без задержек по времени.

Примечание: если момент прилёта и вылета совпадают, то считает, что данный рейс был осуществлён, но из-за технических неполадок произошла посадка в это же время.

Входные данные:

В первой строке входного файла находятся два числа через пробел: число L - общая продолжительность рабочего дня аэропорта (натуральное число, не превышающее 10⁹) и число N - количество запланированных рейсов (натуральное число, не превышающее 10 000). В следующих N строках находится по два числа через пробел. Первое число - время вылета рейса (натуральное число, не превышающее 10⁹). Второе число - время прилета (натуральное число, не превышающее 10⁹).

Пример входного файла:

1000 7

100 200

0 300

200 430

500 550

550 700

700 800

750 900

При таких условиях вылеты можно максимизировать следующим образом: 100-200; 200-430; 500-550; 550-700; 700-800. Поэтому ответ для приведённого примера 5 700.

Запишите в ответе два числа: наибольшее возможное количество вылетов в расписании, а также наименьшее возможное время вылета последнего рейса.