Задача #2147

(Л. Шастин) Игроман по имени Иван обожает проводить время за компьютерными играми, но объем SSD-накопителя, установленного на его любимом ноутбуке, не безграничен. Иван-игроман хочет насладиться очередным шедевром индустрии видеоигр, для установки которого требуется освободить на SSD-накопителе хотя бы M мебибайт памяти. Для этого Иван-игроман подготовил список файлов, которые можно удалить для очистки свободного места на диске. Собранные Иваном метаданные характеризуют тип (он определяется номером от 1 до K) и объем каждого из файлов (выраженный в байтах – b, кибибайтах – kb или мебибайтах – mb). Известно, что можно удалить не более R файлов каждого из K типов. Определите минимальное количество файлов, которые можно удалить так, чтобы освободить хотя бы M мебибайт памяти, а также наименьший возможный объем (в байтах) удаленного при этих условия файла.

Примечание. 1 мебибайт = 2¹⁰ кибибайт = 2²⁰ байт.

Входные данные

В первой строке входного файла находится число N – количество файлов (натуральное число, не превышающее 10 000). Во второй строке находятся три числа: K – количество типов файлов, R – наибольшее количество файлов одного типа, которые можно удалить, и M – минимальный объем памяти (в мебибайтах), который нужно освободить (R < K < M < 1 000 000). В следующих N строках находятся три значения – тип текущего файла, его объем и единица измерения объема (b / kb / mb).

Запишите в ответе два числа: сначала минимальное количество файлов, которые можно удалить так, чтобы освободить хотя бы M мебибайт памяти, а затем наименьший возможный объем (в байтах) удаленного при этих условиях файла.

Типовой пример организации данных во входном файле

7
2 2 600
1 250 mb
2 40 mb
1 102400 kb
1 150 mb
2 204800 kb
2 26214400 b
1 170 mb

При таких исходных данных можно удалить 2 файла типа №1 (250 mb + 170 mb или 250 mb + 150 mb) и 1 файл типа №2 (204800 kb). Минимальный возможный объем удаленного при таких условиях файла = 150 mb = 157286400 b. Ответ: 3 157286400.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.