Задание 26 ЕГЭ по информатике

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

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

Примечание. 1 мебибайт = $2^{10}$ байт, кибибайт = $2^{20}$ байт.

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

В первой строке входного файла находится число $N$ – количество файлов (натуральное число, не превышающее 10000). Во второй строке находятся три числа: $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.

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

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/14625_26.txt