Highest Scoring Keywords

You are given a list of keywords each with an associated score. Your task is to find the top (n) keywords having the highest scores. The keywords must be sorted in descending order by their score. If multiple keywords have the same score, they should appear in the same order as they were given in the input (i.e. a stable sort is required).

Input Format:
The first line contains two integers (m) and (n), where (m) is the total number of keywords and (n) is the number of top keywords to output. The following (m) lines each contain a keyword (a string without spaces) and an integer score separated by a space.

Output Format:
Output exactly (n) lines. Each line should contain the keyword and its score separated by a space, in descending order of score.

inputFormat

The input is read from standard input (stdin). The first line contains two integers (m) and (n) separated by a space. The next (m) lines each contain a keyword and an integer score separated by a space.

outputFormat

Print to standard output (stdout) exactly (n) lines. Each line should consist of a keyword and its score separated by a space, sorted in descending order by their score. If scores are equal, maintain the original input order.## sample

3 2
apple 10
banana 30
cherry 25

banana 30
cherry 25