Поезд следует по магистрали через m населённых пунктов. Известно, что в поезде k мест. Дан список из n заявок на поездку, для каждой из которых известно, на какой станции пассажир собирается садиться, а на какой - выходить. При посадке на станции x контроллёр отдаёт предпочтение пассажиру, который едет дальше остальных, определяя место пассажира, как свободное с минимальным номером (от 1 до k). При этом сначала осуществляется высадка пассажиров, а затем посадка.
Определите, сколько пассажиров смогут добраться до пункта своего назначения и сколько перегонов будут заняты все места в поезде (перегон - участок магистрали между соседними населёнными пунктами).
Входные данные:
В первой строке файла задано три числа: m (2<=m<=2000) - количество населённых пунктов со станциями на магистрали, k (1<=k<=1000) - количество мест в поезде, n (1<=n<=10000) - количество пассажиров, желающих проехать на поезде.
В каждой из следующих n строк располагается пара чисел: сначала номер населённого пункта, откуда пассажир следует, затем номер населённого пункта, в котором пассажир собирается сойти.
Выходные данные:
Два числа: сначала количество пассажиров, которые смогут добраться до нужной им станции, затем количество перегонов, при прохождении которых в поезде будут заняты все места.
Пример входных данных:
10 3 6
2 6
2 4
3 5
3 8
4 9
4 6
При таких исходных данных добрать до нужного пункта смогут 4 пассажира ((2, 6), (2,4), (3, 8), (4, 9)). При этом свободных мест не будет на трёх перегонах (3-4, 4-5, 5-6).
Файл