Description

The selection of volunteers for the World Expo is in full swing in City A. To choose the most suitable candidates, City A held a written test for all applicants. Only those whose written scores reach the interview cutoff can enter the interview. The interview cutoff is set at $150\%$ of the planned admission number. That is, if the plan admits $m$ volunteers, the cutoff score is the score of the contestant ranked at $m \times 150\%$ (rounded down), and all contestants whose written scores are not lower than the cutoff will enter the interview.

Please write a program to determine the interview cutoff score and output the registration IDs and written scores of all contestants who enter the interview.

Input Format

• Line 1: Two integers $n, m$ ($5 \leq n \leq 5000, 3 \leq m \leq n$), separated by a space. Here $n$ is the total number of contestants who registered for the written test, and $m$ is the planned number of volunteers to admit. It is guaranteed that $m \times 150\%$, after rounding down, is less than or equal to $n$.
• Lines $2$ to $n+1$: Each line contains two integers separated by a space: the contestant’s registration ID $k$ ($1000 \leq k \leq 9999$) and written score $s$ ($1 \leq s \leq 100$). It is guaranteed that all registration IDs are distinct.

Output Format

• Line 1: Two integers separated by a space. The first integer is the interview cutoff score; the second integer is the actual number of contestants who enter the interview.
• From line 2 onward: Each line contains two integers separated by a space, the registration ID and written score of a contestant who enters the interview. Output contestants in descending order of written score; for equal scores, sort by ascending registration ID.

6 3 
1000 90 
3239 88 
2390 95 
7231 84 
1005 95 
1001 88

88 5 
1005 95 
2390 95 
1000 90 
1001 88 
3239 88 

Hint

[Sample Explanation]

$m \times 150\% = 3 \times 150\% = 4.5$, which is rounded down to $4$. The cutoff ensuring $4$ people enter the interview is $88$. Since there are ties at $88$, all contestants with scores greater than or equal to $88$ enter the interview, so there are $5$ contestants in total.

NOIP 2009 Junior, Problem 2.

Translated by ChatGPT 5