Аэропорту необходимо оптимизировать расписание вылетов аэропланов. Для этого они получили список всех полетов с указанием времени вылета и времени прилета. Известно, что в небе одновременно может находиться только один аэроплан, поэтому необходимо составить расписание так, чтобы обеспечить максимальное количество вылетов. Если время прибытия одного рейса совпадает со временем вылета другого, то вылет может быть осуществлен без задержек по времени.
Запишите в ответе два целых числа: наибольшее возможное количество вылетов и наименьшее возможное время вылета последнего рейса.
Входные данные представлены в файле 26-107.txt следующим образом. В первой строке файла записаны два числа через пробел: L – общая продолжительность рабочего дня аэропорта (натуральное число, не превышающее 109) и N – количество запланированных рейсов (натуральное число, не превышающее 10 000). В следующих N строках записаны по два натуральных числа, не превышающих 109, через пробел: время вылета рейса и время прилёта.
Пример входного файла:
1000 7
100 200
0 300
200 430
500 550
550 700
700 800
750 900
При таких условиях можно обеспечить 5 полётов: 100-200; 200-430; 500-550; 550-700; 700-800. Ответ: 5 700.