짝지어주기(Paired Up)

농부 존은 소들이 젖을 짤 때 옆에 다른 소가 있어 정신적으로 의지가 되면 젖 짜기가 더 수월해진다는 것을 알게 되었습니다.

그래서 그는 M마리의 소(M은 1,000,000,000 이하의 짝수)를 M/2개의 쌍으로 나누려고 합니다.

각 쌍의 소들은 헛간의 분리된 칸으로 들어가 젖을 짜게 되며, 이 M/2개의 칸에서는 동시에 젖 짜기가 진행됩니다.

문제를 조금 복잡하게 만드는 것은, 농부 존의 소들이 각각 다른 양의 우유를 생산한다는 점입니다.

우유 생산량이 A인 소와 B인 소가 짝을 이룬다면, 두 마리의 젖을 짜는 데 총 A+B의 시간이 걸립니다.

농부 존이 소들을 최적으로 짝지었을 때, 전체 젖 짜기 과정을 완료하는 데 걸리는 '최소 시간'을 구하는 프로그램을 작성하시오.

(모든 쌍의 젖 짜기가 동시에 진행되므로, 전체 과정이 완료되는 시간은 짝지어진 소들의 젖 짜는 시간(A+B) 중 가장 오래 걸리는 칸의 시간입니다.)

입력

첫 번째 줄에 N (1 ≤ N ≤ 100,000)이 주어집니다.

다음 N개의 줄에는 각각 두 정수 x와 y가 공백으로 구분되어 주어집니다. 이는 우유 생산량이 y (1 ≤ y ≤ 1,000,000,000)인 소가 x마리 있음을 의미합니다.

x의 총합은 전체 소의 수인 M과 같습니다.

출력

소들을 최적으로 짝지었을 때, 전체 젖 짜기 과정을 완료하는 데 걸리는 최소 시간을 출력합니다.

예제 입력 1

3
1 8
2 5
1 2

예제 출력 1

10

힌트

예제에서 우유 생산량이 8인 소와 2인 소가 짝을 이루고, 5인 소와 5인 소가 짝을 이룹니다. 이렇게 하면 두 칸 모두 젖을 짜는 데 8+2=10, 5+5=10의 시간이 걸립니다.

젖 짜기는 동시에 진행되므로 전체 과정은 10의 시간이 지난 후 완료됩니다. 다른 방식으로 짝을 지으면 최적의 결과가 나오지 않으며, 반드시 어떤 칸은 젖을 짜는 데 10보다 더 많은 시간이 걸리게 됩니다. (예: 8과 5를 짝지으면 13이 소요됨)

출처

USACO 2017 US Open Contest, Silver