등산

농부 John은 소가 힘든 운동을 하면 더 높은 품질의 우유를 생산한다는 사실을 알아냈다. 그래서 그는 자신의 소 $N$마리($1 \le N \le 25000$)를 근처 산에 올려보냈다가 다시 내려오게 하기로 했다.

$i$번째 소는 산을 오르는 데 $U(i)$의 시간이, 내려오는 데 $D(i)$의 시간이 걸린다. 소들은 가축이라 오르내리는 각 구간마다 농부의 도움이 필요하지만, 형편이 좋지 않아 농부는 John과 그의 사촌 Don 두 명뿐이다. John은 소가 산을 오를 때 안내를 맡고, Don은 소가 산을 내려올 때 안내를 맡는다. 모든 소는 안내자가 필요하고 각 구간에는 농부가 한 명씩만 있으므로, 어느 순간에도 산을 오르는 소는 최대 한 마리(John이 안내), 내려오는 소도 최대 한 마리(Don이 안내)뿐이다. 산을 다 올라온 소들은 Don의 도움을 받아 내려가기 전까지 정상에 잠시 모여 기다릴 수 있다. 소가 내려오는 순서는 올라간 순서와 달라도 된다.

모든 소가 산을 오르내리는 전체 여정을 마치는 데 필요한 최소 시간을 구하여라.

• 첫째 줄: 소의 수 $N$.
• 둘째 줄부터 $N$개의 줄: $i+1$번째 줄에 두 정수 $U(i)$와 $D(i)$가 공백으로 구분되어 주어진다($1 \le U(i), D(i) \le 50000$).

• 첫째 줄: 모든 소가 산을 넘는 데 걸리는 최소 시간을 나타내는 정수 하나.

소 3이 먼저, 그다음 소 1, 마지막으로 소 2의 순서로(오를 때와 내려올 때 모두 같은 순서로) 진행하면 전체 시간은 17이 된다.