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

Строительная организация хочет закупить $K$ различных видов деталей для проведения плановых ремонтных работ, причём деталь каждого вида необходимо закупить в количестве не менее $M$ штук, для чего выделяется бюджет $S$. Виды деталей определяются номерами от 1 до $K$. На имеющуюся в распоряжении сумму средств закупается максимально возможное количество деталей, но обязательно так, чтобы деталей каждого вида было закуплено в количестве не менее $M$ штук. Если существует несколько способов закупить наибольшее количество деталей, выбирается тот, при котором затраченная сумма средств будет минимальной.

Определите максимальное количество деталей, которое удастся закупить, а также при этих условиях наибольшее количество закупленных деталей одного вида.

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

В первой строке входного файла находится число $N$ – количество деталей у продавца (натуральное число, не превышающее 10000). Во второй строке находятся три числа: $K$ – количество видов различных деталей, $S$ – сумма денег, отведенная на закупку деталей, и $M$ – минимальное необходимое для закупки деталей каждого вида количество ($K ⩽ M < N < S$). В следующих $N$ строках находятся пары натуральных чисел (каждое из них не превышает 10000) – вид (номер) детали и её стоимость.

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

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

6

2 70 2

2 25

1 10

1 15

2 20

1 5

1 8

При таких исходных данных будут закуплены 2 детали вида №2 (25 + 20) и 3 детали вида №1 (10 + 5 + 8). Ответ: 5 3.

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

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