Petr and his mates decided to visit fashionable restaurant at the top floor of “Antey” tower. The picture of the city you can see beyond it windows is really astonishing but all good things in a world cost a lot. Including yummy food no doubt. Frankly speaking Petr is just a student and do not have a lot of money and his friends ain’t rich too, so they settled to order less expensive dishes possible, but they do not want to leave restaurant in hunger also.

Menu was very handy — there was not only price for each dish but “filling value” too. This value tells how much people can satisfy their hunger with one portion of the dish. For example stuffed turkey could fulfill four men and beetroot salad will leave you in a half-hunger. As you know Petr was really smart and he instantly noticed that if he will order some substantial but quite expensive dishes he can spend less money compared with ordering a lot of cheap but light of those. Petr at once calculated what exactly he could order to satisfy his and his friends’ hunger fully and spend less money possible. There was more then one way to do so and Petr was not so foolish to order 10 portions of the same kind. Therefore he chose order with maximal number of various dishes.

After coming home Petr decided to help other people in a same situation (he was not only smart but kind also) and to write a program for PDA to perform rapid “best order” calculation. Of course they have to get menu first, but Internet helps a lot nowadays. Yet Petr became drowsy after solid meal and eventually felt asleep. So it’s up to you to finish his work.

First line of an input contains two numbers N and M. First stands for the number of dishes in a menu and second for the total number of eaters (1 ≤ N ≤ 100; 1 ≤ M ≤ 20). Next N lines contain descriptions for dishes — one description per line. Description is made of dish name, dish price and “filling value”. These parts are separated with spaces. Dish name is a sequence of small Latin letters with a length between 1 and 30. Price is a integer number between 1 and 10000. “Filling value” is a number between 0.1 and 10.0 with no more then 3 decimal places.

You are to output optimal order description. First line should contain total cost of the order. Next lines should contain ordered dishes — one dish per line. Each line should contain the dish name and the number of portions separated with space. You must not output different lines with same dish name.