Задача #208

Бизнес-центру необходимо составить расписание мероприятий в конференц зале. В каждый момент времени в зале может проводиться только одно мероприятие. Организаторы мероприятий подали заявки, в которых указано время начала и время окончания их мероприятий. Из данных заявок необходимо составить расписание так, чтобы количество проводимых мероприятий было наибольшим. При этом если одна заявка закончилась, а следующая началась в то же время , то их можно ставить подряд.

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

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

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

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

1000 7

50 200

0 300

200 450

500 550

550 700

700 800

750 900

При таких условиях расписание можно составить из мероприятий: 50-200; 200-450; 500-550; 550-700; 700-800. Поэтому ответ для приведённого примера 5 700.