*(Е. Джобс) На въезде в город оборудована сельскохозяйственная ярмарка. Лотки для продажи стоят с двух сторон дороги с двусторонним движением. С каждой стороны расположено по К мест для торговли. Место бронируется на определенное количество минут, при этом управляющим ярмарки закладывается 15 минут на освобождение места после окончания его аренды. Места, которые расположены вдоль полосы по направлению в город, считаются наиболее прибыльными, поэтому при возможности занимаются в первую очередь. Если свободных мест нет, но новый продавец видит, что на одном из мест предыдущий продавец собирает вещи, то он встает в очередь за ним. При этом он не отличает сколько времени осталось на сбор, если несколько продавцов освобождают свое место. Поэтому встает в очередь за первым по номеру лотка. В случае, когда по направлению в город нет свободных мест, но есть места по направлению из города, продавец выбирает подождать собирающегося продавца с «прибыльной» стороны, если таковые имеются. Если на желаемое время мест нет и ни один из продавцов не собирается, то новый продавец уезжает с ярмарки.
В случае, когда на одно и тоже время претендует несколько продавцов, управляющий делает выбор в пользу продавца, который собирается арендовать место на большее время.
Определите, сколько продавцов смогут занять места, и сколько минут за обозначенный период будут заняты все места по направлению в город (с учетом времени на сборы).
Входные данные представлены в файле 26-131.txt следующим образом. Первая строка входного файла содержит натуральное число N (1 ≤ N ≤ 10000) -- количество потенциальных продавцов и натуральное число K (1 ≤ K ≤ 500) -- количество мест на каждой стороне дороги. В каждой из N следующих строк содержится два числа: Т (1 ≤ Т ≤ 4200) -- время от начала ярмарки в минутах, когда продавец планирует начать торговлю, и Р (1 ≤ Р ≤ 300) -- желаемое время аренды лотка.
Запишите в ответе два числа: количество продавцов, которые смогут арендовать место, и суммарную длительность аренды всех лотков вдоль стороны дороги по направлению в город.
Пример входного файла:
6 2
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 40.
Графически (с сеткой в 5 минут) можно представить работу ярмарки при таких входных данных следующим образом, где зеленый цвет - время торговли, желтый -- время сборов:
