Задание №26: Обработка данных с помощью сортировки

(Е. Джобс) Поезд, в котором К мест (с номерами от 1 до К), следует по магистрали через M населенных пунктов. мест. Дан список из N заявок на поездку, для каждой из которых известно, на какой станции пассажир собирается садиться, а на какой — выходить. При посадке на некоторой станции контроллер отдает предпочтение тому пассажиру, который едет дальше остальных, определяя место пассажира, как свободное с минимальным номером. При этом сначала осуществляется высадка пассажиров, а затем посадка.
Определите, сколько пассажиров смогут добраться до пункта своего назначения и на скольких перегонах в поезде будут заняты все места (перегон – это участок магистрали между соседними населенными пунктами).
Входные данные представлены в файле 26-126.txt следующим образом. Первая строка входного файла содержит три натуральных числа: 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 перегонах (3-4, 4-5 и 5-6). Ответ: 4 3.