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$ 行以兩個空格分隔的整數 $W_i$ 和 $S_i$ 描述乳牛 $i$。

輸出格式

• 第 1 行：一個整數，表示任意使風險最小的最佳順序中所有乳牛的最大風險。

範例

輸入格式 1

3
10 3
2 5
3 3

輸出格式 1

2

說明

將重量 10 的乳牛放在底部。牠托著另外兩頭，倒下風險為 $2+3-3=2$。其他乳牛的倒下風險更低。