На складе требуется разместить N контейнеров различного размера, каждый из которых имеет форму куба. Контейнеры имеют разные цвета, которые обозначаются латинскими буквами. Чтобы сэкономить место, контейнеры вкладывают друг в друга. Один контейнер можно вложить в другой, если а) размер стороны внешнего контейнера превышает размер стороны внутреннего на K и более условных единиц и б) цвета внешнего и внутреннего контейнеров различны. Группу вложенных друг в друга контейнеров называют блоком. Количество контейнеров в блоке может быть любым. Каждый блок, независимо от количества и размера входящих в него контейнеров, а также каждый одиночный контейнер, не входящий в блоки, занимает при хранении одну складскую ячейку.
Определите минимальное количество ячеек, которые потребуются для хранения всех контейнеров, и максимальное количество контейнеров в одном блоке.
Входные данные представлены в файле 26-102.txt следующим образом. В первой строке входного файла записано число N – количество контейнеров (натуральное число, не превышающее 20 000) и число K (1 ≤ K ≤ 1000) – наименьшая допустимая разница размеров вложенных соседних контейнеров. Каждая из следующих N строк содержит натуральное число, не превышающее 10000 – длину стороны очередного контейнера, и латинскую букву, обозначающую цвет этого контейнера.
Пример входного файла:
7 5
2 A
18 B
47 A
16 B
38 A
55 A
48 B
Для такого набора контейнеров можно составить два блока, удовлетворяющих условию: (55, 48, 38, 18, 2), (47, 16). Наибольшее количество контейнеров – в первом блоке – 5. Ответ: 2 5.