Online MIPT programming contest | РУССКИЙ |
<PREV Problem: | NEXT> |
< |
---|
Time limit = 5 seconds
Some company specialize in air transportation. The company earn money by transporting goods. Each good is characterized by weight and profit, which company get by transporting this good. In the next flight company may get aboard from A to B kg of goods. Given the list of goods, you need to decide which of them the company should transport to maximize profit.Input The first line contains three numbers — N A B. The number N stands for number of different kinds of goods (N ≤ 100), 1 ≤ A ≤ B ≤ 10000. Then N lines describing the goods follow. Each line contains P_{i}, M_{i} and Q_{i} — profit company get by transporting one unit of the good, mass of the good in kg and maximum number of goods of this kind to be transported. P, M and Q are positive integers.
Output First line of output should contain maximum total profit the company can get. Then N lines follow, each contains one integer equal to quantity of units of the corresponding good to take in the optimal transport plan. If it is not possible to satisfy the restriction A ≤ total mass ≤ B, output '-1'.
Input#13 90 110 100 30 2 15 7 10 1 1 5 |
Output#1306 2 7 1 |
Author:
Dmitry Korolev
18 May 2003
© acm.mipt DevGroup The page was generated in 170ms |