Связать веник не так уж и трудно. А поскольку спрос на этот высокотехнологичный продукт огромен, то фирмы, производящие веники, должны владеть немалым количеством фабрик. Помогите одной из таких фирм оптимально распределить производство между фабриками. На каждой из фабрик за день могут связать от 0 до K веников. Экономисты фирмы доказали, что себестоимость связанных веников различна: в большинстве случаев чем больше веников свяжет фабрика, тем меньшую себестоимость будет иметь последний связанный веник. Однако могут существовать и более сложные ситуации. В первом приближении вы можете считать зависимость себестоимости веника от его номера линейной.

Первая строка содержит целые числа N и M (1 ≤ N, M ≤ 1000) — количество фабрик и количество веников, которое нужно связать.

Затем следует описание фабрик. В (i+1)-й строке даны параметры i-й фабрики K_i, P_i и Q_i (1 ≤ K_i ≤ 100; 0 ≤ P_i, Q_i ≤ 1000) — максимальное количество веников, которое можно связать за день на i-й фабрике, себестоимость первого веника и себестоимость K_i-го веника на i-й фабрике. Как упоминалось выше, стоимость производства j-го веника линейно зависит от j.

Если фирма не может произвести нужное число веников, выведите максимальное количество веников V, которое может быть произведено.

Кроме того, требуется вывести суммарную стоимость производства M (или V, если невозможно произвести M) веников при оптимальном распределении производства с двумя знаками после десятичной точки.

Формат вывода должен быть таким, как указано в примерах ниже.