호반우가 학교에 지각한 이유 5

어찌저찌 마왕성까지 도착한 호반우는 예전에 시작의 마을에서 구한 운석을 소환하는 마법 카드로 메테오를 만들어 마왕성의 병사들을 한 번에 해치우기로 했다.

호반우는 처음에 최대한 높이 하늘로 올라간 뒤, 그 위치를 시작점으로 삼아 마법 카드 $N$개로 다음 행동을 $N$번 반복하려고 한다.

• 남아있는 마법 카드 중 하나를 고른다.
• 고른 마법 카드에 적힌 양의 정수 쌍이 $a,\,b$일 때 $a$만큼 올라가서 운석을 소환하고, $b$만큼 다시 내려온다.
• 사용한 마법 카드는 불타 사라지므로 다시 쓸 수 없다.

$N$개의 마법 카드로 완성한 메테오의 위력은 각 운석의 지상으로부터의 높이를 모두 더한 값이다. 그런데 호반우가 처음에 하늘로 너무 높이 올라가는 바람에 위력을 계산할 수가 없게 되었다.

그래서 호반우는 $N$장의 카드를 모두 사용했을 때까지 지나는 경로의 최저점을 지상으로 보고 메테오의 위력을 계산하기로 했다. 호반우가 처음에 하늘로 올라갈 때는 $N$장의 카드를 어떤 순서로 쓰더라도 지상에 도달할 수 없을 만큼 높이 올라간다.

호반우가 마법 카드를 사용해 가장 위력이 강한 메테오를 만들 수 있게 도와주자.

첫 번째 줄에 마법 카드의 개수 $N$이 주어진다. $(1 ≤ N ≤ 100\,000)$

두 번째 줄부터 $N$개의 줄에 걸쳐 각 마법 카드에 적힌 양의 정수 쌍 $a,\,b$가 공백을 두고 주어진다. $(1 ≤ a,\,b ≤ 10^{9})$

마법 카드 $N$개를 사용해 만들 수 있는 메테오의 위력 중 최댓값을 출력한다.