가장 긴 검

대장장이가 직사각형 철판만 써서 검 한 자루를 만든다. 주문 조건은 다음과 같다.

• 철판은 절대 자르지 않고, 한 줄로 이어서 용접한다.
• 철판마다 두 변 중 하나를 검의 너비로 쓰고, 남은 한 변의 길이를 검의 길이에 더한다.
• 검 모양이 나오려면 이어 붙인 순서대로 너비가 계속 줄어들어야 한다. 너비가 같거나 더 커지도록 이어 붙일 수 없다.
• 대장장이가 가진 철판 $n$개를 하나도 남기지 않고 모두 쓴다.

이어 붙이는 순서와 철판마다의 방향은 대장장이가 정한다. 검의 길이는 철판마다 더한 변의 길이를 모두 합한 값이다.

만들 수 있는 가장 긴 검의 길이를 구하여라.

첫째 줄에 철판의 개수 $n$이 주어진다. ($1 \le n \le 250000$)

다음 $n$개 줄에 철판 하나의 두 변 길이 $s$와 $t$가 나노미터 단위로 주어진다. ($1 \le s \le t \le 10^9$)

철판 $n$개를 모두 써서 검을 만드는 방법이 있는 입력만 주어진다.

철판 $n$개를 모두 써서 만들 수 있는 가장 긴 검의 길이를 첫째 줄에 출력한다.