산악훈련

훈련교관 엄태관은 훈련병들이 산악훈련 후 더 뛰어난 전투력을 갖춘다는 점을 파악했습니다.

따라서, 그는 N명의 훈련병들을 인근 산에 올라가게 한 다음 내려오게 하는 산악훈련을 실시합니다. 훈련병 i는 산을 오르는 데 U(i) 시간이 걸리고, 다시 내려오는 데 D(i) 시간이 걸립니다. 

산악훈련은 반드시 조교의 1:1 지도가 필요한데, 조교는 태규와 강산이 두 명 뿐입니다. 조교 태규는 훈련병들이 산을 오르는 동안 지도할 계획이고, 조교 강산이는 훈련병들이 산을 내려올 때 지도할 계획입니다. 모든 훈련병들은 조교의 지도가 반드시 필요하기에 한 번에 한 명의 훈련병만 산을 오르고 내려갈 수 있습니다. 훈련병들은 조교 태규의 지도를 받으며 산을 오르고, 내려가기 위해 조교 강산이의 도움을 기다리는 동안 산꼭대기에서 대기할 수 있습니다. 훈련병들은 올라간 순서와 상관없이 내려갈 수 있으며, 산악훈련은 산을 오르고 내려가는 과정을 반드시 거쳐야합니다.

당신은 훈련교관을 도와 모든 N명의 훈련병들이 산악훈련을 수료하는 데 필요한 최소 시간을 계산해야 합니다.

N의 범위 : (1 <= N <= 25,000)

• 줄 1: 훈련병의 수, N.
• 줄 2..1+N: 줄 i+1에는 두 개의 공백으로 구분된 정수가 포함되어 있습니다: U(i)와 D(i) (1 <= U(i), D(i) <= 50,000).

• 줄 1: 모든 훈련병이 산악훈련을 받는 데 필요한 최소 시간을 나타내는 단일 정수.