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.

EI20213FQ2 - Top Highest Net Income

You are given a list of transactions, each of them includes transaction code, product code, selling price, quantity and cost per unit. Your task is to write a program to print top K products which have the highest net income (total revenue – total cost).

Input

-      The first line contains two integer N (the number of transactions) and K (1 ≤ N, K ≤ 105).

-      Each line in the next N lines contains five integers representing a transaction. All of them do not exceed 109

Output

The required list of the products is sorted in descending order of the net income and ascending order of product code.

For each product, print the product code and the net income. Note that, if there are products that have the same net income as the net income of the K-th product, print them too.

Sample

https://drive.google.com/file/d/1FyPiGisW2aMyB51W3mGD1h9iiuECx-AA/view?usp=sharing

Input

Output

5 2

1111 1 1000 2 400

1112 2 100 1 78

1113 1 500 10 350

1114 2 99 1 85

1115 3 100 2 15

 

1 2700

3 170


Added by:Ha Minh Ngoc
Date:2021-07-18
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.