В некотором городе есть сеть ресторанов, имеющая в общей сложности n практически одинаковых залов. Администрации поступило k заявок на проведение в предпраздничный день корпоративных мероприятий. В каждой заявке указано время начала и окончания (от 00:00 до 23:59). Для проведения одного мероприятия нужен целиком один зал (какой конкретно, значения не имеет). После окончания мероприятия нужно не менее получаса для подготовки к следующему мероприятию в этом зале. Требуется удовлетворить как можно большее число заявок. Если можно удовлетворить все, то при этом следует использовать наименьшее число залов.

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

В первой строке содержатся числа n и k (1 ≤ n, k ≤ 100). В каждой из следующих k строк содержится время начала и окончания заявки в формате ЧЧ:ММ-ЧЧ:ММ. Время окончания каждой заявки хотя бы на минуту больше времени её начала.

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

В первой строке выведите два числа - количество заявок p, которые удалось удовлетворить, и количество залов q, которое пришлось задействовать.