우유 짜기 대기열

매일 아침 농부 John의 소 $N$마리가 우유를 짜려고 한 줄로 선다. John은 우유 짜기를 두 단계로 나누었다. 소는 줄을 선 순서 그대로 첫 번째 헛간을 지난 다음 두 번째 헛간으로 들어간다. 첫 번째 헛간에서는 John이 소를 한 마리씩 차례로 짜고, 첫 번째 헛간을 나온 소는 같은 순서로 두 번째 헛간에 들어가 동료 Rob이 짠다.

두 헛간이 하나의 순서를 그대로 따라야 하니 낭비가 생긴다. John이 어떤 소를 짜는 데 오래 걸리면 Rob은 할 일 없이 기다린다. 반대로 John이 너무 빨리 짜면 두 번째 헛간 앞에 긴 대기열이 쌓인다.

소 $i$는 첫 번째 헛간에서 $A_i$, 두 번째 헛간에서 $B_i$만큼 시간이 걸린다. 마지막 소의 우유 짜기가 가장 이르게 끝나도록 소의 순서를 정하고, 그때의 완료 시각을 구하라.

규칙은 다음과 같다.

• 시각 $0$에 첫 번째 헛간이 일을 시작한다.
• 각 헛간은 한 번에 소 한 마리만 처리하고, 한번 시작한 소는 중간에 멈추지 않는다.
• 소는 첫 번째 헛간에서 짜기가 끝나야 두 번째 헛간에 들어갈 수 있다.
• 두 헛간은 같은 순서를 쓰고, 대기열에서 기다리는 소의 수에는 제한이 없다.

첫째 줄에 소의 수 $N$이 주어진다. ($1 \le N \le 25000$)

다음 $N$개 줄 가운데 $i$번째 줄에는 소 $i$의 $A_i$와 $B_i$가 공백 하나로 구분되어 주어진다. ($1 \le A_i, B_i \le 20000$)

소의 순서를 최적으로 정했을 때 모든 소의 우유 짜기가 끝나는 가장 이른 시각을 한 줄에 출력한다.