시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

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.

예제 입력 1

2
1 1
3 0

예제 출력 1

2 4

예제 입력 2

2
3 1
1 0

예제 출력 2

4 4

예제 입력 3

3
3 1
1 0
1 0

예제 출력 3

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 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$.