<PREV Problem:
NEXT>
Solved by 244 users: ...
UserDateAttemptTimeCMSC
Zaurbek_I21 mar 2007Kylix3103.52221 
TheVice29 mar 2007Kylix3503.53221 
Quazar09 may 2010FPC103.54221 
TheVice29 mar 2007Kylix3303.50224 
Vladimir_Lee21 mar 2007Kylix3503.03240 
Philip_PV14 jul 2008C++500.10245 
Philip_PV14 jul 2008C++400.10249 
DAV17 jun 2009C++600.04273 
grom17 nov 2003FPC3?.??275 
yalalalala25 sep 2007FPC1102.66276 
Vladislav_Simonenko23 apr 2006FPC602.06279 
yalalalala25 sep 2007FPC1002.65279 
DAV17 jun 2009C++500.04285 
DAV17 jun 2009C++400.04289 
DAV17 jun 2009C++300.04291 
mishik08 sep 2007C++400.08292 
mishik08 sep 2007C++300.08294 
Languages
C++
129
FPC
77
Kylix
18
C
16
Java
13
Ruby
1
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

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 190ms

SW soft NIX
ID = 3.228.11.9