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

(Н. Кургуз) В поезде, состоящем из M вагонов (вагоны пронумерованы от 1 до M), размещаются N групп людей, в каждой из которых не более 4 человек, среди них могут быть дети. Каждый вагон содержит K четырёхместных купе, а также K двухместных боковых блоков. Каждая группа, в которой больше двух человек, размещается в отдельном купе, а каждая группа из 1 или 2 человек – в отдельном боковом блоке или купе. Разделять группы нельзя. В первую очередь размещаются группы с большей численностью, а при равной численности приоритет получают те, в которых больше детей. Группы размещаются на первом подходящем месте в вагоне с наименьшим номером. Определите наибольшее количество детей, которых удастся разместить в поезде, а также номер вагона, в котором останется наибольшее количество свободных мест. Если таких вагонов несколько, укажите наименьший номер подходящего вагона.
Входные данные представлены в файле 26-145.txt следующим образом. Первая строка входного файла содержит натуральное число N (1 ≤ N ≤ 1000) – количество групп, желающих попасть на поезд. Во второй строке записаны два натуральных числа, не превышающих 10 000: M – количество вагонов, и K – количество купе и боковых блоков в одном вагоне. Каждая из следующих N строк описывает одну группу и содержит два целых количество людей в группе и количество детей среди них.
Запишите в ответе два числа: сначала наибольшее количество детей, которое поедут в поезде, затем номер вагона с наибольшим количеством свободных мест.
Пример входного файла:

12
2 2
3 1
3 0
1 0
2 0
4 2
3 2
2 0
4 1
3 1
2 1
3 2
1 0

При таких исходных данных смогут заселиться группы (4,2), (4,1), (3,2), (3,2), (2,1), (2,0), (2,0), (1,0), в 1 вагоне свободных мест – 0, во втором – 3. Ответ: 8 2.