Входной файл содержит информацию о домашках учеников Турбо, отправивших свои решения кураторам в течение календарных суток. В домашке указаны время начала и время окончания приёма работы (в минутах от начала суток).

Рабочие места кураторов пронумерованы натуральными числами начиная с 1. Приём одной работы ученика берёт свободный куратор в окне с минимальным номером. Новый ученик может обратиться к освободившемуся куратору начиная со следующей минуты после завершения приёма предыдущего. Если в момент обращения свободных кураторов нет, ученик уходит спать. Определите, сколько учеников смогут получить проверку домашек в течение 24 ч, и каков номер куратора, который начнёт принимать домашку последним. Если таких номеров несколько, укажите наименьший номер.

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

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

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

Типовой пример организации данных во входном файле

2
5
30 60
40 100
59 60
61 100
101 144
  

При таких исходных данных воспользоваться проверкой смогут первый, второй, четвёртый и пятый ученики. Наименьший номер куратора, где последняя домашка будет принята, - 1, так как будут свободны окна 1 и 2.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.