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

На складе требуется разместить N контейнеров различного размера, каждый из которых имеет форму куба. Контейнеры имеют разные цвета, которые обозначаются латинскими буквами. Чтобы сэкономить место, контейнеры вкладывают друг в друга. Один контейнер можно вложить в другой, если а) размер стороны внешнего контейнера превышает размер стороны внутреннего на K и более условных единиц и б) цвета внешнего и внутреннего контейнеров различны. Группу вложенных друг в друга контейнеров называют блоком. В блок можно объединять до M контейнеров включительно. Каждый блок, а также каждый одиночный контейнер, не входящий в блоки, занимает при хранении одну складскую ячейку. Блоки собирают по одному, начиная с самого большого контейнера. В него добавляют самый большой из оставшихся, подходящий по размеру и имеющий минимальный подходящий код цвета.
Определите минимальное количество ячеек, которые потребуются для хранения всех контейнеров, и количество блоков, которые содержат максимально возможное число контейнеров.
Входные данные представлены в файле 26-103.txt следующим образом. В первой строке входного файла записано число N (1 ≤ N ≤ 20000) – количество контейнеров, число K (1 ≤ K ≤ 1000) – наименьшая допустимая разница размеров вложенных соседних контейнеров и число M (1 ≤ M ≤ N) – наибольшее допустимое количество контейнеров в блоке. Каждая из следующих N строк содержит натуральное число, не превышающее 10000 – длину стороны очередного контейнера, и латинскую букву, обозначающую цвет этого контейнера.
Пример входного файла:

7 5 3
2 A
18 B
47 A
16 B
38 A
55 A
48 B

Для такого набора контейнеров можно составить три блока, удовлетворяющих условию: (55, 48, 38), (47, 18, 2) и (16). Количество блоков с максимальным количеством контейнеров – 2. Ответ: 3 2.