В городе расположены постаматы из K ячеек. Ячейки постамата пронумерованы, начиная с 1. Курьеры складывают товар в ячейки постамата. Товар кладётся в свободную ячейку с минимальным номером. Известно время размещения товара в ячейку и время освобождения ячейки (в минутах от начала суток). Товар достаётся из ячейки в течение минуты. Начиная со следующей минуты, в ячейку можно положить другой товар. Если все ячейки заняты, то товар убирается в другой постамат.

Определите количество товаров, которое можно загрузить в первый постамат за 24 часа и номер последней использованной ячейки, в которую положили товар.

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

В первой строке входных данных задается количество ячеек в постамате - K и количество товаров, которые хотят убрать в постамат - M.

В каждой из последующих М строк содержится два числа - количество минут с начала суток, предположительное время занятия ячейки и количество минут - предположительное время, когда товар заберёт покупатель.

В ответе укажите 2 числа слитно (без пробелов и других разделителей)