ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

USU Championship 2004

About     Problems     Submit solution     Judge status     Standings
Contest is over

E. Enterprise

Time limit: 2.5 second
Memory limit: 64 MB
To bind a broom it’s a hard work. As there is a very big demand for this high-tech product an brooms binding enterprise is to have a big amount of production workshops. You are to help such an enterprise to allocate the work among the workshops. Each workshop can bind from 0 to K brooms a day. Economists of the enterprise found out that each bound broom has a different prime cost: in most cases the more brooms were bound a day the less prime cost has the last broom bound that day. However, there may be more complicated situations. As a first approximation you may assume every dependence linear. So decided the economists when they determined a dependence of the next in turn broom’s prime cost on the industrial output of the workshop. You are to find out the optimal work load of the workshops.

Input

The first line contains two integers N and M (1 ≤ NM ≤ 1000) — an amount of workshops and the required industrial output of brooms, respectively.
Then workshops description follows. The (i+1)-st line describes the i-th workshops with three numbers Ki, Pi, and Qi (1 ≤ Ki ≤ 100; 0 ≤ PiQi ≤ 1000) — they are the maximal number of brooms that can be bound at the i-th workshop a day, the prime cost of the first broom and the prime cost of Ki-th broom at the i-th workshop. As it was mentioned above the cost of j-th broom’s production is the linear with respect to j function.

Output

If the enterprise can’t produce the required number of brooms your program is to output the maximal number of brooms V that can be bound at the enterprise.
Besides, you are to output the total costs on production of M (or V if the enterprise can’t bind M) brooms with optimal allocation of industrial outputs within two digits after a decimal point.
The output format is to be as in sample outputs below.

Samples

inputoutput
2 10
6 20 15
100 100 100
Minimum possible cost: 505.00
2 10
5 30 14
1 20 20
Maximum possible amount: 6
Minimum possible cost: 130.00
Problem Author: Magaz Asanov and Pavel Egorov
Problem Source: USU Championship 2004
To submit the solution for this problem go to the Problem set: 1342. Enterprise