(А. Богданов) В гостинице составляют недельный план уборки номеров после отъезда клиентов. Все номера одинаковые и пронумерованы с 1 до К. В основе плана -- журнал заявок, в каждой из которых записано время заезда и время выезда для N заявок. Заявки поступают в случайном порядке. На начало недели все номера подготовлены к заселению. После отъезда клиента на уборку номера отводится 30 минут. Уборка начинается в следующую минуту после освобождения номера. Клиент может заезжать в подготовленный номер в следующую минуту после окончания уборки. Если подготовленных номеров несколько, то выбирается номер с максимальным временем простоя; из номеров с одинаковым временем простоя -- последний номер. Если подготовленных номеров нет, клиент ждет первый подготовленный номер; при этом время отъезда не меняется. Если первый номер будет готов после запланированного времени отъезда, клиент не ждёт и сразу уезжает.
Определите максимальное время ожидания клиента перед заселением и последний номер, заселенный в течение этой недели.
Входные данные представлены в файле 26-117.txt следующим образом. В первой строке входных данных задается два числа: K -- количество номеров (1 ≤ K ≤ 1000) и N -- количество заявок (1 ≤ N ≤ 100000). В каждой из последующих N строк указано время заезда и время выезда в минутах, начиная с 0:00 воскресенья.
Запишите в ответе два числа: максимальное время ожидания клиента перед заселением и последний номер, заселенный в течение этой недели.
Пример входного файла:
2 5
10 30
15 40
40 65
55 80
56 100
При таких исходных данных первый клиент в минуту 10 сразу заезжает в номер 2, в 15-ю минуту второй клиент заезжает в номер 1 (без ожидания). На 30-й минуте первый клиент выезжает из номера 2 и в этом номере сразу начинается уборка, которая заканчивается на 60-й минуте. Поэтому третий клиент, который хотел заселиться на 40-й минуте, будет ждать 21 минуту и заселится в номер 2 на 61-й минуте. Аналогично четвёртый клиент, который хотел заселиться на 55-й минуте, должен ждать 16 минут, потому что готовый номер 1 будет готов только на 40 + 30 + 1 = 71 минуте. Последний клиент, желающий заселиться на 56-й минуте, фактически сможет сделать это только на 65 + 30 + 1 = 96 минуте, так что он будет ждать 40 минут и заселится в номер 2. Ответ: 40 2.