Задача #2146

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

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

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

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

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

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.

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