Solved by 244 users: ...
UserDateAttemptTimeCMSC
Zaurbek_I`21 mar 2007`Kylix3103.52221
TheVice`29 mar 2007`Kylix3503.53221
Quazar`09 may 2010`FPC103.54221
TheVice`29 mar 2007`Kylix3303.50224
Vladimir_Lee`21 mar 2007`Kylix3503.03240
Philip_PV`14 jul 2008`C++500.10245
Philip_PV`14 jul 2008`C++400.10249
DAV`17 jun 2009`C++600.04273
grom`17 nov 2003`FPC3?.??275
yalalalala`25 sep 2007`FPC1102.66276
Vladislav_Simonenko`23 apr 2006`FPC602.06279
yalalalala`25 sep 2007`FPC1002.65279
DAV`17 jun 2009`C++500.04285
DAV`17 jun 2009`C++400.04289
DAV`17 jun 2009`C++300.04291
mishik`08 sep 2007`C++400.08292
mishik`08 sep 2007`C++300.08294
 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 DevGroupThe page was generated in 190ms