케이크

옛날 옛적, 몹시도 가난한 래글랜드 왕국에 (거지들의) 왕과 왕비가 살고 있었다. 두 사람에게는 매력적인 외동딸 포퍼렐라가 있었는데, 아름답고 엄청난 부자인 골드티스 왕자와 결혼하기로 되어 있었다. 어린 공주는 반대했지만, 부모는 결혼식을 자신들의 성에서 올려야 한다고 고집했다. 그들은 솜씨 좋은 요리사에게 결혼식 케이크 — 래글랜드의 유명한 결혼식 케이크 — 를 준비해 달라고 부탁했다. 하지만 (왕과 왕비치고는) 그리 넉넉하지 못한 탓에, 요리사는 단 한 명뿐이고 오븐도 작은 것 하나뿐이라 모든 케이크를 그 하나의 오븐에서 구워야 한다.

요리사는 서로 다른 케이크 $N$개를 만들어야 한다. 케이크 하나를 만드는 과정은 두 단계로 이루어진다. 첫 번째 단계에서 요리사는 반죽을 만들어 틀에 넣고, 두 번째 단계에서 그 케이크를 오븐에 굽는다. $i$번째 케이크의 반죽을 만드는 데는 $a_i$초가 걸리고, 반죽이 준비된 뒤 케이크를 굽는 데는 $b_i$초가 걸린다. (반죽이 준비되었다고 해서 곧바로 구울 필요는 없으며, 틀에 담긴 채로 얼마든지 기다릴 수 있다.) 요리사는 한 번에 하나의 반죽만 만들 수 있고, 오븐에서는 한 번에 하나의 케이크만 구울 수 있다. 케이크를 준비하고 굽는 순서는 자유롭게 정할 수 있다.

모든 케이크를 완성하는 데 필요한 최소 시간을 구하여라. 오븐을 다루는 데(케이크를 넣고 다 구워진 케이크를 꺼내는 데) 걸리는 시간은 0으로 가정한다.

첫째 줄에 만들어야 하는 케이크의 수 $N$ ($N \le 1{,}000{,}000$)이 주어진다. 이어지는 $N$개의 줄에는 각각 두 정수 $a_i$, $b_i$ ($1 \le a_i, b_i \le 2{,}000{,}000{,}000$)가 주어진다. $a_i$는 $i$번째 케이크의 반죽을 만드는 데 걸리는 시간이고, $b_i$는 굽는 데 걸리는 시간이다.

모든 케이크를 완성하는 데 필요한 최소 시간을 한 줄에 출력한다. 답은 $2{,}000{,}000{,}000$을 넘지 않음이 보장된다.