환상의 듀오

찬호는 친구들이 서로가 옆에 있을 때 게임을 더 잘한다는 것을 알게 됩니다. 그래서 그는  $M$ ($M \leq 1,000,000,000$, $M$ even)를명의 친구들을 $M/2$ 쌍으로 짝을 지으려고 합니다. 그 다음 각 쌍들은 각자의 방에서 게임을 하게됩니다. 이 $M/2$개의 방에서는 게임이 동시에 진행될 것입니다.

복잡한 점은, 각 친구는 게임에서 다른 점수를 얻는다는 사실입니다.점수가 $A$와 $B$인 친구들이 짝을 이루면, 그들이 게임을 완료하는 데 총 $A+B$ 시간 단위가 소요됩니다.

찬호가 친구들을 최적의 방법으로 짝을 지어주는 것을 가정하고, 모든 게임을 완료하는 데 걸리는 최소 시간을 계산해주세요.

입력의 첫 번째 줄에는 $N$ ($1 \leq N \leq 100,000$)이 포함됩니다. 다음 $N$줄 각각은 두 개의 정수 $x$와 $y$를 포함하며, 이는 찬호가 각각 점수가 $y$인 $x$ 친구를 가지고 있다는 것을 나타냅니다 ($1 \leq y \leq 1,000,000,000$). $x$의 합은 $M$, 총 소의 수입니다.

친구들을 최적으로 짝 지었을 때 찬호의 친구들이 모든 게임을 완료하는데 필요한 최소 시간을 출력하세요.