|
Маскарад
(Время: 1 сек. Память: 16 Мб Сложность: 63%)
По случаю введения больших новогодних каникул устраивается великий праздничный бал-маскарад. До праздника остались считанные дни, поэтому срочно нужны костюмы для участников. Для пошивки костюмов требуется L метров ткани. Ткань продается в N магазинах, в которых предоставляются скидки оптовым покупателям. В магазинах можно купить только целое число метров ткани. Реклама магазина номер i гласит "Мы с радостью продадим Вам метр ткани за Pi рублей, однако если Вы купите не менее Ri метров, то получите прекрасную скидку — каждый купленный метр обойдется Вам всего в Qi рублей". Чтобы воплотить в жизнь лозунг "экономика страны должна быть экономной", правительство решило потратить на закупку ткани для костюмов минимальное количество рублей из государственной казны. При этом ткани можно купить больше, чем нужно, если так окажется дешевле. Ответственный за покупку ткани позвонил в каждый магазин и узнал, что:
- реклама каждого магазина содержит правдивую информацию о ценах и скидках;
- магазин номер i готов продать ему не более Fi метров ткани.
Ответственный за покупку очень устал от проделанной работы и поэтому поставленную перед ним задачу «закупить ткань за минимальные деньги» переложил на своих помощников. Напишите программу, которая определит, сколько ткани нужно купить в каждом из магазинов так, чтобы суммарные затраты были минимальны.
Входные данные
В первой строке входного файла записаны два целых числа N и L (1 ≤ N ≤ 100, 0 ≤ L ≤ 100). В каждой из последующих N строк находится описание магазина номер i — 4 целых числа Pi, Ri, Qi, Fi (1 ≤ Qi ≤ Pi ≤ 1000, 1 ≤ Ri ≤ 100, 0 ≤ Fi ≤ 100).
Выходные данные
В выходной файл OUTPUT.TXT выведите минимально возможную стоимость материи. Если покупка невозможна, выведите -1.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 2 14
7 9 6 10
7 8 6 10
| 88 |
| 2 | 1 20
1 1 1 1
| -1 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
