알고리즘 겨울 캠프에 참여한 \(N\)명의 점심을 위해 유명한 업체인 두솥도시락에 \(N\)개의 여러 다양한 도시락을 주문했다.

도착한 도시락들은 냉장고에 잘 정리해 두었지만,

점심 시간이 되어서야 도시락을 데우는 데 쓸 전자레인지가 하나밖에 없다는 사실을 깨달았다.

이 전자레인지는 출력이 작기 때문에 한 번에 하나의 도시락만 데울 수 있다.

도시락을 다 데운 즉시 다음 도시락을 데울 수 있고, 데워진 도시락은 바로 먹을 수 있다. 각 도시락마다 데우는 시간과 먹는 시간이 다를 수 있다.

예를 들어 \(N = 2\)에 대해 첫 번째 도시락의 데우는 시간이 \(1\), 먹는 시간이 \(1\)이고 두 번째 도시락의 데우는 시간이 \(2\), 먹는 시간이 \(2\)이면

차례대로 도시락을 데웠을 때 첫 번째 도시락은 \(1 + 1 = 2\)의 시간에 다 먹을 수 있고, 두 번째 도시락은 \(1 + 2 + 2 = 5\)의 시간에 다 먹을 수 있다.

점심 시간이 지체되면 알고리즘을 위한 프로그램을 진행하는데 차질이 생기기 때문에, 가장 빠른 시간에 점심 시간을 끝내려고 한다.

점심 시간이 시작될 때부터 도시락을 데우기 시작하고, 모든 사람이 도시락을 다 먹으면 점심 시간이 끝난다.

어느 순서로 도시락을 데워야 가장 빨리 점심 시간을 마칠 수 있을까?

입력

• 첫 번째 줄에 도시락의 수 \(N\)이 주어진다.\((1 ≤ N ≤ 100)\)
• 그 다음 줄부터 \(N\)개의 줄에 정수 \(a\) \(b\)가 주어진다. 이는 도시락을 데우는 시간이 \(a\), 먹는데 걸리는 시간이 \(b\)라는 뜻이다.\((1 ≤ a ≤ 100, 1 ≤ b ≤ 100)\)

출력

• 도시락을 데우는 순서를 변경할 수 있을 때, 가장 빨리 마칠 수 있는 점심 시간을 출력한다.

입력 예시 1

3
1 1
2 2
3 1

출력 예시 1

7

예시 1 설명

도시락을 차례대로 데우면 첫 번째 도시락은 \(1 + 1 = 2\)의 시간에, 두 번째 도시락은 \(1 + 2 + 2 = 5\)의 시간에, 세 번째 도시락은 \(1 + 2 + 3 + 1 = 7\)의 시간에 먹을 수 있다.

입력 예시 2

3
2 4
2 4
2 1

출력 예시 2

8