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

문제

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

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

• 남아있는 마법 카드 중 하나를 선택한다.
• 선택한 마법 카드에 적혀있는 양의 정수 쌍이 $a,,円b$일때 $a$만큼 상승하여 운석을 소환하고 $b$만큼 다시 하강한다.
• 사용한 마법 카드는 불타 사라지기에 다시 사용할 수 없다.

$N$개의 마법 카드를 사용하여 완성한 메테오의 위력은 각 운석들의 지상으로부터의 높이의 합이지만 호반우가 처음에 하늘로 너무 높이 올라가는 바람에 메테오의 위력을 계산할 수가 없게 되었다!

결국 호반우는 시작점으로부터 $N$장의 카드를 모두 사용했을 때까지의 경로 중 최저점을 지상이라 생각하여 메테오의 위력을 계산하기로 하였다. 호반우가 처음에 하늘로 올라갈 때 $N$장의 카드를 어떤 순서로 사용하더라도 지상에 도달할 수 없을 만큼 높이 올라간다고 한다.

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

입력

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

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

출력

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

제한

힌트