문제

승우는 알고리즘 스터디원들이 서로를 도와가며 문제를 해결할 때 효율이 올라간다는 사실을 발견했다. 그래서 승우는 $M$명의 스터디원($M \le 1\,000\,000\,000$, $M$은 짝수)을 $M/2$개의 쌍으로 나누려고 한다. 각 쌍은 별도의 스터디룸에서 동시에 문제를 풀기 시작한다.

각 스터디원이 문제를 해결하는 데 걸리는 시간은 서로 다를 수 있다. 만약 문제 해결 시간이 $A$인 사람과 $B$인 사람이 한 쌍이 된다면, 해당 쌍이 문제를 모두 해결하는 데는 총 $A+B$의 시간이 걸린다.

승우는 모든 스터디원이 문제를 해결할 때까지 걸리는 전체 시간을 최소화하고 싶다. 즉, 각 쌍의 소요 시간 중 최댓값이 가장 작아지도록 짝을 짓고자 한다. 스터디원들을 최적으로 짝 지었을 때, 모든 쌍이 문제를 해결하기까지 걸리는 시간의 최솟값을 구하시오.

입력

첫째 줄에 스터디원의 종류를 나타내는 $N$이 주어진다. ($1 \le N \le 100\,000$) 이어서 $N$개의 줄에 두 정수 $x$와 $y$가 공백으로 구분되어 주어진다. 이는 문제 해결 시간이 $y$인 스터디원이 $x$명 있음을 의미한다. ($1 \le y \le 1\,000\,000\,000$) 모든 $x$의 합은 전체 스터디원 수 $M$이다.

출력

스터디원들을 최적으로 짝 지었을 때, 모든 쌍이 문제를 해결하는 데 걸리는 시간의 최솟값을 출력한다.

예제 입력 1

3
1 8
2 5
1 2

예제 출력 1

10