등산 (Mountain Climbing)

속초로 워크샵을 떠난 N명의 선생님들은 설악산을 등산하기로 하였다.

i번째 선생님은 산을 올라가는 데 U(i)만큼의 시간이, 내려가는 데 D(i)만큼의 시간이 걸린다.

등산 초보인 선생님들을 위하여 산신령 A는 올라가는 선생님들을 봐 주고, 산신령 B는 내려가는 선생님들을 봐 주기로 하였다.

모든 선생님이 도움을 받아야 하고, 각 방향에는 한 명의 산신령만이 있기 때문에, 어느 시점에서도 산신령 A의 도움을 받는 최대 한 명의 선생님만 산을 올라갈 수 있으며, 마찬가지로 산신령 B의 도움을 받는 최대 한 명의 선생님만 산을 내려갈 수 있다.

산을 올라왔지만 내려가기를 기다리는 선생님들이 산 꼭대기에 다수 있을 수 있고, 선생님들은 올라온 순서와 다른 순서로 내려갈 수 있다.

N명의 선생님들이 모두 등산을 끝마치는데 걸리는 최소 시간을 구하여라.

입력

첫 번째 줄에 N이 주어진다. (1 \le N \le 25,000)

두 번째 줄부터 N개의 줄에, U(i)와 D(i)가 주어진다. (1 <= U(i), D(i) <= 50,000)

출력

첫 번째 줄에, 등산을 모두 마치는 데 걸리는 최소 시간을 출력한다.

예제1

등산을 3, 1, 2번 순서로, 하산을 같은 순서로 정하면 시간이 17만큼 소요된다.

출처

USACO January 2012 Silver

등산 (Mountain Climbing) 1초 128MB