문제

영우는 빈 시간을 그냥 흘려보내는 것을 못 견디는 효율 중시형 사람이다. 어느 날 영우는 여러 작업을 처리해야 하는 상황이 되었고, 각 작업은 전처리와 후처리 두 단계로 이루어져 있다는 사실을 알게 되었다.

$i$번째 작업의 전처리에는 $A_i$시간이 걸리고, 후처리에는 $B_i$시간이 걸린다. 한 작업의 후처리는 반드시 그 작업의 전처리가 모두 끝난 뒤에만 시작할 수 있다.

전처리는 영우가 직접 집중해서 처리해야 하므로 동시에 최대 $1$개만 진행할 수 있다. 반면 후처리는 자동으로 진행되기 때문에, 전처리가 끝난 작업이라면 여러 작업의 후처리를 동시에 진행할 수 있다.

작업들의 전처리 순서를 자유롭게 정할 수 있을 때, 모든 작업의 전처리와 후처리가 끝나는 데 걸리는 최소 시간을 구해보자.

입력

첫째 줄에 작업의 개수 $N$이 주어진다. $(1 \le N \le 200,000)$

다음 $N$개의 줄에 걸쳐, $i$번째 줄에는 $i$번째 작업의 전처리 시간 $A_i$와 후처리 시간 $B_i$가 공백으로 구분되어 주어진다. $(1 \le A_i, B_i \le 10^9)$

출력

모든 작업을 완료하기 위한 최소 시간을 출력하시오.

예제 입력 1

3
1 2
3 4
5 6

예제 출력 1

12