21247번 - Lost Island 다국어

There is an island far away occupied by a tribe. Among people in this tribe, $n$ eye colors occur: there are $a_i$ people with the eye color $i$ ($a_i > 0$), and there are no other colors known to the tribe. More formally, the members of the tribe know the value of $n$, but they don't know that all eye colors actually occur (that all $a_i > 0$). The tribe follows a specific religion: if someone can deduce their own eye color, they commit suicide the next day. It must be said, the people in the tribe are incredibly smart.

Once, at day 0, a traveler arrives to the island, meets the tribe and says $n$ true sentences, in which $b_i \ge 0$, and at least one $b_i > 0$:

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

Find the last day when the suicides will take place and the total number of people committed 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 > 0$) --- the number of people with the eye color $i$ and the lower bound of this number said by the traveler.

Output two integers --- the number of the last day when the suicides will take place, and the total number of people committed suicide.

Let's show what happens in the first sample.

The person with the eye color $1$ doesn't see anyone with the eye color $1$ around, but hears that there is at least one person with this color. So they deduce who can be this person and commit suicide at the day $1$.

All other people know that only two colors occur and that one person with the eye color $1$ is dead. So they deduce all of them have eye color $2$ and commit suicide at the day $2$.