Farmer John의 소 $N$마리($1 \le N \le 50{,}000$, 번호 $1..N$)는 도망쳐 서커스에 들어가려 합니다. 발굽 때문에 줄타기와 공중 그네를 할 수 없고(지난번 대포로 소를 쏘는 시도도 참패했습니다), 곡예를 연습하기로 했습니다.

소들은 창의적이지 않아 서로 위에 서서 어떤 높이의 수직 탑을 만드는 곡예 하나만 생각했습니다. 탑에서 어떤 순서로 서야 할지 고민합니다.

각 소는 무게($1 \le W_i \le 10{,}000$)와 힘($1 \le S_i \le 1{,}000{,}000{,}000$)이 있습니다. 쓰러질 위험은 위에 있는 모든 소의 총 무게(자신은 제외)에서 자신의 힘을 뺀 값입니다. 더 강한 소일수록 위험이 작습니다. 모든 소의 최대 위험을 최소화하는 순서를 구하세요.

입력

• 1번째 줄: 정수 $N$.
• $2..N+1$번째 줄: $i+1$번째 줄은 소 $i$를 공백 구분 정수 $W_i$, $S_i$로 나타냅니다.

출력

• 1번째 줄: 위험을 최소화하는 임의의 최적 순서에서 모든 소의 최대 위험을 나타내는 정수 하나.

예제

입력 1

3
10 3
2 5
3 3

출력 1

2

참고

무게 10인 소를 맨 아래에 놓습니다. 다른 두 소를 받치므로 위험은 $2+3-3=2$입니다. 다른 소의 위험은 더 작습니다.