<PREV Problem:
NEXT>
Solved by 244 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Maximum profit

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 ≤ AB ≤ 10000. Then N lines describing the goods follow. Each line contains Pi, Mi and Qi — 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#1
3 90 110
100 30 2
15 7 10
1 1 5

Output#1
306
2
7
1


Author:
Dmitry Korolev
18 May 2003

<PREV | Problem set | Search related messages | NEXT>


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

SW soft NIX
ID = 54.162.181.75