<ПРЕД Задача:
СЛЕД>
Задачу решили 244 пользователя: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Максимизация прибыли

Time limit = 5 секунд

Некоторая компания занимается авиаперевозками. Компания получает прибыль от перевозки товаров. Каждый товар имеет определенный вес и прибыль, получаемую компанией от его перевозки.

На очередной рейс компания может загрузить от A до B килограмм полезного груза. И мея набор товаров требуется определить, какие из них следует отправить для максимизации прибыли.

Вход На первой строке записаны числа N A B, где N — число различных видов товаров (N ≤ 100), 1 ≤ AB ≤ 10000. Затем на N строках записана информация о товарах в формате Pi Mi Qi — соответственно, прибыль, получаемая с единицы перевезенного товара, масса единицы товара и количество единиц данного товара, доступное для перевозки. P, M и Q — натуральные числа.

Выход На первой строке выведите максимальную суммарную прибыль, полученную компанией. Затем на N строках выведите по одному целому числу — количество перевозимых единиц соответствующего товара. Если прибыль получить невозможно, то выведите в качестве ответа "-1".

Вход#1
3 90 110
100 30 2
15 7 10
1 1 5

Выход#1
306
2
7
1


Автор:
Дмитрий Королев
18 Мая 2003

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 170ms

SW soft NIX
ID = 3.214.184.250