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

1570. Ужин на 45 этаже

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Problem illustration
Петя и его друзья впервые пришли в ресторан, расположенный на последнем этаже небоскреба Антей. Из его окон открывается прекраснейший вид на город! Естественно, за такое удовольствие надо платить — цены в ресторане приличные. Но друзья — всего лишь студенты. Oни не могут себе позволить роскошь, и поэтому решили обойтись самыми дешевыми блюдами, однако уходить голодными тоже не собирались.
Меню в ресторане оказалось очень удобным — напротив каждого блюда, кроме цены, была указана его сытность, то есть количество людей, которых оно способно насытить. Например, индейкой можно насытить четверых, а винегретом не наестся даже один. Петя смекнул, что не всегда выгодно брать самое дешевое блюдо — лучше взять подороже и накормить побольше людей. Он быстро произвел расчеты и выяснил, какой набор блюд будет наиболее выгодным. Однако заказывать 10 винегретов ему тоже не хотелось, поэтому среди всех оптимальных вариантов заказа он выбрал такой, в котором присутствует наибольшее количество разных блюд.
После этого похода в ресторан Петя решил написать программу для своего КПК, чтобы в следующий раз просто скачать меню из интернета и в один момент получить оптимальный набор блюд. Помогите ему в этом.

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

Первая строка содержит целые числа N и M — количество блюд в меню ресторана и количество друзей в компании (1 ≤ N ≤ 100; 1 ≤ M ≤ 20). В каждой из следующих N строк перечислено по одному пункту из меню: через пробел указаны название блюда, цена в рублях и сытность. Название блюда состоит из строчных латинских букв и имеет длину от 1 до 30. Названия всех блюд различны. Цена — целое число от 1 до 10000. Сытность блюда — число от 0.1 до 10.0, записанное не более чем с тремя знаками после десятичной точки.

Результат

Выведите оптимальный заказ. В первой строке выведите сумму заказа. В каждой из следующих строк перечислите по одному блюду из заказа в формате
<название> <количество>
Одно и то же блюдо не должно повторяться в списке дважды.

Пример

исходные данныерезультат
4 6
pizza 320 2.4
turkey 1050 3.5
lasagna 150 0.9
pasta 75 0.45
865
pizza 2
lasagna 1
pasta 1
Автор задачи: Владимир Яковлев
Источник задачи: XII Чемпионат УрГУ по программированию, 6 октября, 2007