№727715911
Отель расположен на берегу моря и состоит из небольших домиков, расположенных линиями от моря по К домов в линию. Первая линия домиков расположена на берегу. Перед сезоном все домики подготовлены к заселению. Все заявки на заселение записываются в журнал по мере поступления. В каждой заявке указан час заезда и час выезда, отсчёт ведётся от начала сезона. Домик считается свободным в следующий час после выезда. Домик для заселения выбирается в момент приезда. Турист всегда заселяется в первый свободный домик ближайшей к морю линии, где есть свободные домики. Определить максимальный номер линии, в которой будет заселяться хотя бы один домик и количество заселенных домиков в следующий час после заселения последнего туриста.
Входные данные представлены в файле следующим образом. Первая строка входного файла содержит два натуральных числа, записанных через пробел: К (1 ≤ K ≤ 100) - количество домиков в одной линии, и N (1 ≤ N ≤ 106) - количество заявок. Каждая из N последующих строк описывает содержит два целых числа: час заезда и час выезда, считая от начала сезона.
В ответе запишите два целых числа: максимальный номер линии, в которой будет заселяться хотя бы один домик и количество заселенных домиков в следующий час после заселения последнего туриста.
Пример входного файла:
3 5
7 65
10 40
16 33
35 55
39 46
При таких исходных данных в линии по три домика. В первый день будут заселены все три домика первой линии. На следующий день заселят освободившийся дом на 1-й линии и один дом на 2-й линии. После 39 ч в отеле будет занято 4 домика. Ответ: 2 4.