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 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 i-th workshop a day, the prime cost of the first broom and the prime cost of K_i-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.