EIU Programming Practices and Exams

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 ≤ 10⁵).

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

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