407886: GYM102916 J 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 in 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 who 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 who committed suicide.

2
1 1
3 0

2 4

2
3 1
1 0

4 4

3
3 1
1 0
1 0

3 3

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 on 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 on day $$$2$$$.