(А. Богданов) Проводится вычислительный эксперимент для определения необходимого количества самокатов на разных парковках города в начальный момент времени. Всего есть M парковок с номерами от 1 до М. Поступило всего N заявок на аренду самокатов. В каждой заявке указано время начала аренды в минутах от начала суток, продолжительность аренды, а также номера парковок старта и финиша. Определите сколько всего нужно самокатов, чтобы все заявки были выполнены, и какое наибольшее число самокатов в какой-то момент будут в аренде одновременно. Будем считать, что заряда самоката хватает на весь день и самокат может быть арендован со следующей минуты после окончания предыдущей аренды.
Входные данные представлены в файле 26-123.txt следующим образом. Первая строка входного файла содержит два натуральных числа, записанных через пробел: M (1 ≤ M ≤ 100) -- количество парковок, и N (1 ≤ N ≤ 106) -- количество заявок. Каждая из N последующих строк описывает содержит четыре целых числа: время начала аренды в минутах от начала суток, длительность аренды в минутах, номер парковки старта и номер парковки финиша.
В ответе запишите два числа: сначала необходимое количество самокатов, затем наибольшее количество самокатов, которые в какой-то момент будут в аренде одновременно.
Пример входного файла:
2 3
1 4 2 2
3 6 1 1
5 9 1 2
При таких исходных данных нужно три самоката: два в начале размещаются на парковке 1 и один -- на парковке 2. Одновременно в аренде находятся максимум два самоката (с 3-й по 8-ю минуту включительно). Ответ: 3 2.