소 D는 세계 일주 여행을 준비하고 있습니다. 출발하기 전에 그는 계획에 따라 목록에 있는 $n$개의 물자 준비 작업을 완료해야 하며, 이 작업들은 처음에 순서대로 $1, 2, \dots, n$으로 번호가 매겨져 있습니다.

현재 물자의 수량을 정수 $x$라고 하면, 처음에는 $x = 0$입니다. $i$번째 작업은 두 양의 정수 $a_i, b_i$로 설명되며, 해당 작업을 수행할 때 다음 변화가 차례대로 일어납니다.

1. 먼저 $x$를 $a_i$만큼 증가시킵니다(즉, $x \leftarrow x + a_i$로 둡니다).
2. 그다음 $x$의 크기를 확인합니다. 만약 이때 $x > b_i$이면, $x$를 $b_i$로 줄입니다(즉, $x \leftarrow \min(x, b_i)$로 둡니다).

작업 수행을 시작하기 전에, 소 D는 목록의 순서에 대해 최대 한 번의 조정을 할 수 있습니다. 작업 중 하나를 임의로 골라 꺼낸 뒤 수열의 맨 끝으로 옮기며, 나머지 작업들의 상대적인 순서는 그대로 유지됩니다(아무런 조정도 하지 않는 것을 선택할 수도 있습니다).

조정을 마친 후, 소 D는 새로운 순서에 따라 앞에서부터 뒤로 차례대로 모든 $n$개의 작업을 수행하며, 각 작업은 정확히 한 번씩 수행됩니다. 소 D는 모든 작업이 끝난 후 물자의 수량 $x$가 될 수 있는 최댓값이 얼마인지 알고 싶어 합니다.

입력

stdin에서 데이터를 읽어들인다.

첫째 줄에 작업의 개수를 나타내는 양의 정수 $n$이 주어진다.

다음 $n$개의 줄 중 $i$번째 줄에는 $i$번째 작업의 매개변수를 설명하는 두 양의 정수 $a_i, b_i$가 주어진다.

출력

stdout에 출력한다.

한 줄에 하나의 정수를 출력하며, 이는 모든 작업이 끝난 후 물자 수량 $x$의 가능한 최댓값을 나타낸다.

예제

입력 1

3
1 100
100 90
1 1

출력 1

90

참고

$2$번째 작업을 수열의 맨 끝으로 옮기면, 작업 수행 순서는 $1, 3, 2$가 됩니다. 각 작업이 끝난 후 $x$의 값은 차례대로 $1, 1, 90$이 됩니다.

만약 $1$번째 작업을 맨 끝으로 옮기면 최종적으로 $x = 2$가 되고, 순서를 조정하지 않거나 $3$번째 작업을 맨 끝으로 옮기면 최종적으로 $x = 1$이 됩니다. 따라서 $x$의 가능한 최댓값은 $90$입니다.

예제 2

참가자 디렉터리 아래의 supply/supply2.in과 supply/supply2.ans를 참조하라.

이 예제는 테스트 케이스 $1 \sim 4$의 제약 조건을 만족한다.

예제 3

참가자 디렉터리 아래의 supply/supply3.in과 supply/supply3.ans를 참조하라.

이 예제는 테스트 케이스 $5 \sim 6$의 제약 조건을 만족한다.

예제 4

참가자 디렉터리 아래의 supply/supply4.in과 supply/supply4.ans를 참조하라.

이 예제는 테스트 케이스 $7 \sim 10$의 제약 조건을 만족한다.

제한

모든 데이터에 대해 $1 \le n \le 2 \times 10^5$, $1 \le a_i, b_i \le 10^9$임이 보장된다. 주의: 데이터는 $a_i \le b_i$를 보장하지 않는다.

이 문제는 총 $10$개의 테스트 케이스로 구성되어 있으며, 각 테스트 케이스는 $10$점이고 독립적으로 채점된다. 자세한 데이터 범위는 아래 표와 같다.

특수 성질 A: $b_1 = b_2 = \dots = b_n$.