№722272901

В одной волшебной местности живут гномы, которые любят варить зелья в магических котлах. Всего есть P котлов, они пронумерованы, в начальный момент все они свободны. Гномы варят зелья в порядке общей очереди. Первый в очереди гном, желающий сварить зелье, подходит к свободному котлу с наименьшим номером. Если котел ранее не использовался, гном может начать варить зелье сразу, а если уже использовался - только через две минуты после того, как он подошел к такому котлу. Одна порция зелья варится 1 минуту.

На заварку одной порции зелья гном тратит две единицы маны (магической энергии для заварки зелий). Если в один момент подошли несколько гномов, то варить зелье идёт тот, у кого запас маны меньше. Гном будет варить зелья, пока у него достаточно маны для их заварки. Гном, у которого осталось меньше двух единиц маны, не может сварить зелье и уходит.

Известно время в минутах от начала суток, когда каждый гном подошёл к котлам, и количество маны у гнома.

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

Входные данные представлены в файле следующим образом. Первая строка входного файла содержит два натуральных числа: D - количество гномов (1 ≤ D ≤ 100000) и P - количество котлов (1 ≤ P ≤ 1000). В каждой из последующих D строк содержится информация по одному гному: время подхода гнома к котлам (в минутах с начала суток) и количество имеющейся у него маны.

В ответе запишите два числа: количество порций зелья, сваренных гномами за сутки, и наибольшее количество порций зелья, которое смог сварить один гном.

Пример входного файла:

5 2

1 6

4 9

3 1

4 5

9 11

При таких исходных данных за сутки было сварено 14 порций зелья. Наибольшее количество порций (5) было сварено гномом с количеством маны 11. Гном с количеством маны 1 сразу же уходит, т. к. у него недостаточно маны для заварки хотя бы одной порции зелья. Ответ: 14 5.