호텔의 수건 준비표

문제

한 호텔에서는 저녁마다 객실에 추가로 전달할 수건을 준비한다. 투숙객은 안내 데스크에 필요한 수건 수를 여러 번 요청할 수 있고, 직원들은 요청이 들어올 때마다 별도의 기록을 남긴다. 같은 객실의 요청이 여러 기록으로 나뉘어 있으면 준비 과정에서 빠뜨리기 쉬우므로, 관리자는 객실별 요청을 합친 준비표를 만들려고 한다. 각 요청 기록에는 객실 번호 R과 추가로 필요한 수건 수 A가 적혀 있다. 모든 요청은 새로 추가된 요청이다. 따라서 같은 객실 번호가 다시 등장하더라도 이전 요청을 취소하거나 수건 수를 덮어쓰는 것이 아니다. 해당 객실의 모든 기록에 적힌 A를 더한 값이 그 객실에 준비해야 할 수건의 총수이다. 입력에는 취소 기록이나 이미 전달한 수건의 기록이 없다. 준비표에는 요청 기록이 한 번 이상 등장한 객실만 적는다. 각 객실은 기록의 개수와 관계없이 준비표에 정확히 한 번 나타나야 한다. 호텔에 실제로 존재하더라도 입력에 등장하지 않은 객실은 준비표에 적지 않는다. 객실 번호는 정수이며, 번호가 연속되어 있다고 가정할 수 없다. 직원들은 수건이 많이 필요한 객실부터 물품을 챙긴다. 따라서 준비표의 객실은 수건 총수가 많은 순서로 배치한다. 수건 총수가 같은 객실이 여러 개이면 객실 번호가 작은 객실을 먼저 배치한다. 요청이 들어온 순서나 마지막으로 요청한 시점은 준비표의 순서에 영향을 주지 않는다. 관리자는 완성된 준비표의 행 수와 각 행의 내용을 확인하려고 한다. 주어진 모든 요청을 객실별로 합친 뒤 정해진 순서대로 준비표를 출력한다. 요청 기록은 적어도 하나 주어지고, 각 기록의 수건 수는 양수이므로 준비표에 적을 객실도 반드시 하나 이상 존재한다.

입력

첫째 줄에 요청 기록의 수를 나타내는 정수 N이 주어진다. 1 ≤ N ≤ 50,000이다.
다음 N개의 줄에 정수 R과 A가 공백으로 구분되어 주어진다. 1 ≤ R ≤ 9,999, 1 ≤ A ≤ 9이다. 같은 객실 번호가 여러 번 주어질 수 있다.

출력

첫째 줄에 준비표에 포함되는 서로 다른 객실의 수 K를 출력한다. 다음 K개의 줄에 객실 번호와 해당 객실의 수건 총수를 공백으로 구분하여 출력한다. 수건 총수의 내림차순으로 출력하고, 총수가 같으면 객실 번호의 오름차순으로 출력한다.

6
203 2
101 4
203 3
305 5
101 1
410 2

4
101 5
203 5
305 5
410 2

3
88 9
88 1
88 2

1
88 12

4
9 1
2 3
7 2
1 3

4
1 3
2 3
7 2
9 1

출처: Devin.KR 자체 제작