На въезде в город оборудована сельскохозяйственная ярмарка. Лотки для продажи стоят с двух сторон дороги с двусторонним движением. С каждой стороны расположено по K мест для торговли. Место бронируется на определенное количество минут, при этом управляющим ярмарки закладывается 15 минут на освобождение места после окончания его аренды. Места, которые расположены вдоль полосы по направлению в город, считаются наиболее прибыльными, поэтому при возможности занимаются в первую очередь. Если свободных мест нет, но новый продавец видит, что на одном из мест предыдущий продавец собирает вещи, то он встает в очередь за ним. При этом он не отличает сколько времени осталось на сбор, если несколько продавцов освобождают свое место. Поэтому встает в очередь за первым по номеру лотка. В случае, когда по направлению в город нет свободных мест, но есть места по направлению из города, продавец выбирает подождать собирающегося продавца с «прибыльной» стороны, если таковые имеются. Если на желаемое время мест нет и ни один из продавцов не собирается, то новый продавец уезжает с ярмарки.
В случае, когда на одно и тоже время претендует несколько продавцов, управляющий делает выбор в пользу продавца, который собирается арендовать место на большее время.
Определите, сколько продавцов смогут занять места, и сколько минут за обозначенный период будут заняты все места по направлению в город (с учетом времени на сборы).
Входные данные:
В первой строке файла содержится два числа K (1 ≤ K ≤ 500) – количество мест на каждой из сторон дороги и N (1 ≤ N ≤ 10000) – количество потенциальных продавцов.
В каждой из N следующих строк содержится два числа: T (1 ≤ T ≤ 4200) – время от начала ярмарки в минутах, когда продавец планирует начать торговлю, и P (1 ≤ P ≤ 300) – желаемое время аренды лотка.
Выходные данные:
Два числа: количество продавцов, которые смогут занять место, и суммарную длительность аренды всех лотков вдоль стороны дороги по направлению в город.
Пример входных данных:
2 6
1 10
11 25
16 15
21 25
26 20
31 10
Обозначим лотки, как 1В и 2В (выгодный) со стороны в город, и 1Н, 2Н (невыгодный) – из города.
Тогда
1 продавец: 1В – 1-10 минут + 15 минут на сборы (лоток занят с 1 по 25 минуты)
2 продавец: 2В – 11-35 минут + 15 минут на сборы (лоток занят с 11 по 50 минуты)
3 продавец: 1В – дождаться, пока соберется предыдущий, 26-40 + 15 минут на сборы (лоток занят с 26 по 55 минуты)
4 продавец: 1Н – 21-45 + 15 минут на сборы (лоток занят с 21 по 60 минуты)
5 продавец: 2Н – 26-45 + 15 минут на сборы (лоток занят с 26 по 60 минуты)
6 продавец уезжает с ярмарки
При этом все места с выгодной стороны будут заняты 40 минут (с 11 до 50).
Графически (с сеткой в 5 минут) можно представить работу ярмарки при таких входных данных следующим образом, где зеленый цвет – время торговли, желтый – время сборов:
