미리듣기 공통 음량

문제

음악 스트리밍 서비스에서 새로 공개할 곡의 미리듣기 음량을 정하려고 한다. 이번 미리듣기는 모든 청취자에게 같은 음량으로 제공되며, 서비스가 선택할 수 있는 음량은 1 이상 100 이하의 정수다. 곡마다 별도의 음량을 정하거나 청취자에 따라 음량을 바꾸는 기능은 사용하지 않는다. 서비스는 사전 조사에 참여한 N명의 청취자에게 편하게 들을 수 있는 음량 범위를 물었다. i번 청취자의 응답은 두 정수 L_i와 R_i로 주어지며, 선택한 음량 V가 L_i 이상 R_i 이하일 때 그 청취자는 미리듣기 음량에 만족한다. 범위의 양 끝값도 만족하는 음량에 포함한다. 범위 안에서는 어느 음량을 선택하더라도 만족의 정도가 같으며, 범위 밖의 음량은 얼마나 가까운지와 관계없이 만족하지 않는 것으로 처리한다. 조사 응답 하나는 청취자 한 명을 나타낸다. 여러 청취자가 같은 범위를 제출했더라도 각각 별도의 한 명으로 센다. 모든 응답은 올바른 범위이며, 응답을 수정하거나 일부 청취자를 조사에서 제외할 수는 없다. 음량을 선택하는 데 드는 비용이나 청취자별 가중치는 없다. 서비스는 만족하는 청취자 수가 가장 많아지는 음량을 선택한다. 가장 많은 청취자를 만족시키는 음량이 여러 개라면 그중 가장 작은 음량을 선택한다. 만족하는 청취자 수가 같은 구간의 가운데 음량을 고르는 등의 다른 기준은 적용하지 않는다. 조사 응답을 바탕으로 최종 음량과 그 음량에 만족하는 청취자 수를 구하는 프로그램을 작성한다. N은 1 이상이고 모든 응답 범위는 비어 있지 않으므로, 적어도 한 명을 만족시키는 음량은 항상 존재한다.

입력

첫째 줄에 청취자 수 N이 주어진다.
다음 N개의 줄에 각 청취자의 응답 L_i와 R_i가 공백으로 구분되어 주어진다.
모든 입력값은 정수이며, 1 ≤ N ≤ 1,000, 1 ≤ L_i ≤ R_i ≤ 100이다.

출력

첫째 줄에 선택할 음량과 그 음량에 만족하는 청취자 수를 공백으로 구분하여 출력한다. 만족하는 청취자 수를 최대로 하고, 동점이면 가장 작은 음량을 출력한다.

4
10 20
15 25
18 18
30 40

18 3

3
1 1
100 100
50 50

1 1

3
7 12
7 12
7 12

7 3

출처: Devin.KR 자체 제작