짝 짓기

농부 존의 소는 곁에 다른 소가 있어 마음이 든든할 때 젖을 더 쉽게 짠다. 그래서 존은 $M$마리의 소($M \le 1\,000\,000\,000$, $M$은 짝수)를 $M/2$개의 쌍으로 나누려 한다. 각 쌍은 헛간의 서로 다른 칸으로 가서 젖을 짜고, $M/2$개 칸의 착유는 동시에 진행된다.

소마다 우유 생산량이 다르다. 생산량이 $A$인 소와 $B$인 소를 한 쌍으로 묶으면 두 마리의 젖을 모두 짜는 데 $A+B$만큼의 시간이 걸린다.

존이 소를 가장 잘 짝지었을 때, 전체 착유가 끝나기까지 걸리는 시간의 최솟값을 구하시오.

첫째 줄에 $N$($1 \le N \le 100\,000$)이 주어진다. 다음 $N$개의 줄에는 각각 두 정수 $x$와 $y$가 주어지며, 우유 생산량이 $y$($1 \le y \le 1\,000\,000\,000$)인 소가 $x$마리 있다는 뜻이다. $x$의 합이 전체 소의 수 $M$이다.

소를 최적으로 짝지었을 때 모든 소의 젖을 짜는 데 걸리는 최소 시간을 출력한다.

예제에서 생산량이 8인 소와 2인 소를 짝짓고, 5인 소 두 마리를 짝지으면 두 칸 모두 착유에 10만큼의 시간이 걸린다. 착유는 동시에 진행되므로 전체 과정은 10만큼의 시간 뒤에 끝난다. 다른 방법으로 짝지으면 어느 한 칸에서 10보다 오래 걸리므로 최적이 아니다.