На складе требуется разместить 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.