Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

EIHPROFIT - The highest profitable product

 

 

Your store has n products, each product has unique identity. Given the cost, the price and the number of items you sold last month for each product, find out the top k highest profit products. Note that if some products have same profit as the k-highest profit product, output them too.

Input

The first line contains two integers n and k (k ≤ n ≤ 105).

Each line in the next n lines contains product’s identity, product’s name, the price, the cost and the quantity you sold.

Note: All integers are less than 2*10^5

Output

The list of top highest profit products which are in order of decreasing the total profit, and increasing identity. Each product output product’s identity, product’s name and the total profit

Sample

Input

Output

4 2

1 laptop 10 8 3

2 watch 20 17 2

3 phone 100 87 1

4 glasses 10 9 5

3 phone 13

1 laptop 6

2 watch 6


Added by:Ha Minh Ngoc
Date:2019-12-16
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.