You work in a Gold Store. Every item in the store has different weight and price. And, you have two safe deposit boxes. The first safe box is stronger than the other one and it can properly hold at most m items.

Because everyday several items are sold and several other new items arrive to the store, you want to write a program which decides what items to choose for the first safe box. Items are put in descending order according to their price per unit weight. If two items have the same unit price, then the item with the smaller id is before the other one.

Question: Write a program that is going to read n item information, then it will show top m items to store in the first safe box.

Input specification
You will be given two integers (n and m) the number of items and top m items to show where 0 ≤ n, m ≤ 3000. Then, in the following n lines you will be given three information for each item:

• ID: an integer between 1 and 1e6
• Weight: an integer between 1 and 1e5
• Price: an integer between 0 and 1e8

Output specification
Show the ID and unit price of top m items.