Обработка данных с сортировкой

На въезде в город оборудована сельскохозяйственная ярмарка. Лотки для продажи стоят с двух сторон дороги с двусторонним движением. С каждой стороны расположено по 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 минут) можно представить работу ярмарки при таких входных данных следующим образом, где зеленый цвет – время торговли, желтый – время сборов: