잃어버린 섬

먼 곳의 섬에 한 부족이 살고 있다. 이 부족에는 $n$개의 눈 색깔이 있으며, 눈 색깔 $i$를 가진 사람은 $a_i$명이다($a_i > 0$). 부족이 알고 있는 눈 색깔은 이것이 전부다. 정확히 말하면, 부족은 $n$의 값은 알지만 모든 $a_i > 0$인지는 알지 못한다.

이 부족은 특별한 종교를 따른다. 자신의 눈 색깔을 추론할 수 있는 사람은 다음 날 자살한다. 부족 사람들은 매우 영리하다.

0일차에 한 여행자가 섬에 도착해 부족을 만나고, $b_i \ge 0$이고 적어도 하나의 $b_i > 0$인 참인 문장 $n$개를 말한다.

• 와, 눈 색깔 1인 사람이 적어도 $b_1$명 있다!
• 와, 눈 색깔 2인 사람이 적어도 $b_2$명 있다!
• ...
• 와, 눈 색깔 $n$인 사람이 적어도 $b_n$명 있다!

자살이 마지막으로 일어나는 날과, 자살한 사람의 총수를 구하라.

첫 줄에 눈 색깔의 수인 정수 $n$ ($2 \le n \le 200000$)이 주어진다.

다음 $n$개의 줄에는 각각 두 정수 $a_i$와 $b_i$ ($1 \le a_i \le 10^9$, $0 \le b_i \le a_i$, 적어도 하나의 $b_i$는 0보다 크다)가 주어진다. $a_i$는 눈 색깔 $i$를 가진 사람의 수이고, $b_i$는 여행자가 말한 이 수의 하한이다.

자살이 마지막으로 일어나는 날의 번호와, 자살한 사람의 총수를 두 정수로 출력한다.

첫 번째 예제에서 무슨 일이 일어나는지 보자. 눈 색깔이 1인 사람은 주변에 같은 색 눈을 가진 사람이 없지만, 그 색을 가진 사람이 적어도 한 명 있다는 말을 듣는다. 그 사람은 누가 그 한 명일 수 있는지 따져 보고, 1일차에 자살한다.

나머지 사람들은 눈 색깔이 두 가지뿐이라는 것과 눈 색깔 1인 사람 한 명이 죽었다는 것을 안다. 그래서 모두 눈 색깔이 2라고 추론하고, 2일차에 자살한다.