ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1342. Фирма веников не вяжет

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

Исходные данные

Первая строка содержит целые числа N и M (1 ≤ NM ≤ 1000) — количество фабрик и количество веников, которое нужно связать.
Затем следует описание фабрик. В (i+1)-й строке даны параметры i-й фабрики Ki, Pi и Qi (1 ≤ Ki ≤ 100; 0 ≤ PiQi ≤ 1000) — максимальное количество веников, которое можно связать за день на i-й фабрике, себестоимость первого веника и себестоимость Ki-го веника на i-й фабрике. Как упоминалось выше, стоимость производства j-го веника линейно зависит от j.

Результат

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

Примеры

исходные данныерезультат
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
Автор задачи: Магаз Асанов и Павел Егоров
Источник задачи: USU Championship 2004