To bind a broom it’s a hard work. As there is a very big demand for this hightech 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 ≤ 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 ith workshops with three numbers K_{i}, P_{i}, and Q_{i} (1 ≤ K_{i} ≤ 100;
0 ≤ P_{i}, Q_{i} ≤ 1000) — they are the maximal number of brooms that can be bound at the ith workshop a day, the prime cost of the first broom and the prime cost of K_{i}th broom at the ith workshop. As it was mentioned above the cost of jth 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
input  output 

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