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.
The first line contains two integers N and M (1 ≤ N, M ≤ 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 ≤ Pi, Qi ≤ 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.
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.
6 20 15
100 100 100
Minimum possible cost: 505.00
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