Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
spagetti
Обычно макаронные изделия продают в пачках или в пакетах. А вот фирма
"Бесконечность" освоила выпуск гибкой лапши, которая продаётся на метры, как тесьма или альпинистские верёвки. Лапша реализуется через интернет-магазин и очень популярна у покупателей. Фирма получает R рублей прибыли с каждого метра проданной лапши и ещё по Z рублей с каждого выполненного заказа за доставку.
Сегодня поступили N заказов на лапшу. А имеется всего одна катушка
лапши, на которой осталось M метров ценного продукта. Возможно, все заказы выполнить
не удастся - но количество выполненных заказов должно быть как
можно больше, ведь невыполненный заказ вредит репутации фирмы.
Какую максимальную прибыль может получить фирма от реализации этой
катушки лапши при описанных выше условиях?
Входные данные. В первой строке - натуральные числа
R, Z, M и N, разделённые пробелами. В следующей строке -
N разделённых пробелами натуральных чисел, заказанные длины лапши.
Все входные значения не превышают 1000.
Выходные данные. Одно целое число - максимальная прибыль, которую сможет получить фирма от реализации имеющейся лапши по поступившим заказам.
Пример. При следующих входных данных
20 3 11 7
7
2
4
3
1
6
5
программа должна вывести число 232. Именно такую прибыль
можно получить, если выполнить заказы на 2, 3, 1 и 5 м лапши:
220 руб. за 11 м лапши и ещё 12 руб. за 4 доставленных заказа.
Для отправки решений необходимо выполнить вход.
|