Lost Island

An island far away is home to a tribe. The tribe has $n$ eye colors. There are $a_i$ people with eye color $i$ ($a_i > 0$), and the tribe knows of no other colors. Strictly speaking, the tribe knows the value of $n$ but does not know that every $a_i > 0$.

The tribe follows a religion in which anyone who can deduce their own eye color commits suicide the next day. The people of the tribe are extremely clever.

On day 0, a traveler arrives on the island, meets the tribe, and makes $n$ true statements, where $b_i \ge 0$ and at least one $b_i > 0$.

• Wow, there are at least $b_1$ people with eye color 1!
• Wow, there are at least $b_2$ people with eye color 2!
• ...
• Wow, there are at least $b_n$ people with eye color $n$!

Find the last day on which suicides take place, and the total number of people who commit suicide.

The first line contains an integer $n$ ($2 \le n \le 200000$), the number of eye colors.

Each of the next $n$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i \le 10^9$, $0 \le b_i \le a_i$, at least one $b_i$ is greater than 0). Here $a_i$ is the number of people with eye color $i$, and $b_i$ is the lower bound on that number stated by the traveler.

Print two integers: the number of the last day on which suicides take place, and the total number of people who commit suicide.

Here is what happens in the first sample. The person with eye color 1 sees no one else with that color but hears that at least one person has it. They work out who that person could be and commit suicide on day 1.

Everyone else knows that only two colors exist and that one person with eye color 1 has died. They conclude that all of them have eye color 2 and commit suicide on day 2.