Поезд, в котором К мест (с номерами от 1 до К), следует по магистрали через M населенных пунктов. мест. Дан список из N заявок на поездку, для каждой из которых известно, на какой станции пассажир собирается садиться, а на какой — выходить. При посадке на некоторой станции контроллер отдает предпочтение тому пассажиру, который едет дальше остальных, определяя место пассажира, как свободное с минимальным номером. При этом сначала осуществляется высадка пассажиров, а затем посадка.

Определите, сколько пассажиров смогут добраться до пункта своего назначения и на скольких перегонах в поезде будут заняты все места (перегон – это участок магистрали между соседними населенными пунктами).

Входные данные представлены в файле следующим образом. Первая строка входного файла содержит три натуральных числа: M (2 ≤ M ≤ 2000) – количество населенных пунктов со станциями на магистрали, K (1 ≤ K ≤ 1000) – количество мест в поезде и N (1 ≤ N ≤ 10000) – количество пассажиров, желающих проехать на поезде.

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

Пример работы программы: