경매

여러 사람이 하나의 물건을 사려고 할 때, 각 참여자는 자신이 낼 가격을 제시한다. 보통 경매에서는 가장 높은 가격을 제시한 사람에게 물건을 팔지만, 어떤 방식에서는 가장 낮은 가격을 기준으로 물건을 팔기도 한다.

그런 방식에서는 모든 사람이 가장 낮은 금액만 제시할 수 있으므로, 같은 가격을 제시한 사람이 둘 이상이면 그 가격은 경쟁력이 떨어진다고 본다. 따라서 다음 규칙으로 낙찰자를 정한다.

먼저, 제시된 가격들 중에서 그 가격을 제시한 사람의 수가 가장 적은 가격을 찾는다. 그런 가격이 여러 개라면 가장 낮은 가격을 선택한다. 마지막으로, 선택된 가격을 제시한 사람들 중 가장 먼저 그 가격을 제시한 사람이 물건을 살 수 있다.

각 참여자가 이름과 가격을 제시한 순서대로 주어질 때, 낙찰자의 이름과 낙찰 가격을 구하시오.

첫째 줄에 두 정수 U와 N이 주어진다. U는 제시할 수 있는 가격의 상한이고, N은 입찰 횟수이다.

• 1 ≤ U ≤ 10,000
• 1 ≤ N ≤ 100,000

다음 N개의 줄에는 이름 S와 가격 P가 입찰 순서대로 주어진다.

• S는 공백이 없는 알파벳 대소문자로 이루어져 있으며 길이는 10자 이하이다.
• 1 ≤ P ≤ U
• P는 정수이다.

낙찰자의 이름과 낙찰 가격을 한 줄에 공백으로 구분해 출력한다.