Петя и его друзья впервые пришли в ресторан, расположенный на последнем этаже небоскреба Антей. Из его окон открывается прекраснейший вид на город! Естественно, за такое удовольствие надо платить — цены в ресторане приличные. Но друзья — всего лишь студенты. Oни не могут себе позволить роскошь, и поэтому решили обойтись самыми дешевыми блюдами, однако уходить голодными тоже не собирались.

Меню в ресторане оказалось очень удобным — напротив каждого блюда, кроме цены, была указана его сытность, то есть количество людей, которых оно способно насытить. Например, индейкой можно насытить четверых, а винегретом не наестся даже один. Петя смекнул, что не всегда выгодно брать самое дешевое блюдо — лучше взять подороже и накормить побольше людей. Он быстро произвел расчеты и выяснил, какой набор блюд будет наиболее выгодным. Однако заказывать 10 винегретов ему тоже не хотелось, поэтому среди всех оптимальных вариантов заказа он выбрал такой, в котором присутствует наибольшее количество разных блюд.

После этого похода в ресторан Петя решил написать программу для своего КПК, чтобы в следующий раз просто скачать меню из интернета и в один момент получить оптимальный набор блюд. Помогите ему в этом.

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

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