Bảo tàng thành phố có \(N\) bức tranh được đánh số thứ tự từ \(1\) đến \(N\). Bức tranh thứu \(i\) có kích thước là \(A_{i}\) và được định giá là \(B_{i}\) \((1 \leq i \leq N)\).

Giám đốc bảo tàng muốn chọn một số bức tranh trưng bày trong buổi triển lãm để thu được lợi nhuận lớn nhất thỏa mãn các tiêu chí:

• Phải trưng bày ít nhất một bức tranh.
• Chênh lệch về kích thước giữa các bức tranh được trưng bày càng nhỏ càng tốt.
• Tổng giá trị các bức tranh được trưng bày là lớn nhất.

Gọi \(A_{min}\) là kích thước nhỏ nhất, \(A_{max}\) là kích thước lớn nhất, \(S\) là tổng giá trị của các bức tranh được lựa chọn trưng bày. Lợi nhuận của bảo tàng được tính theo công thức \(H = S - (A_{max} - A_{min})\).

Yêu cầu: Hãy giúp Giám đốc bảo tàng tìm \(H\) lớn nhất?.

Input

• Dòng đầu tiên chứa số nguyên \(N\) là số lượng các bức tranh \((2 \leq 500000)\).
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa hai số nguyên \(A_{i}\) và \(B_{i}\) là kích thước và định giá của bức tranh thứ \(i\) \((1 \leq A_{i} \leq 10^{15}, 1 \leq B_{i} \leq 10^{9}, 1 \leq i \leq N)\)

Output

• Số nguyên \(H\) lớn nhất tìm được.

Example

3
2 3
9 2
4 5

6

Ràng buộc

• Có \(25\%\) số test tương ứng \(25\%\) số điểm có \(N \leq 16\).
• Có \(25\%\) số test tương ứng \(25\%\) số điểm có \(N \leq 300\).
• Có \(25\%\) số test tương ứng \(25\%\) số điểm có \(N \leq 5000\).
• Có \(25\%\) số test tương ứng \(25\%\) số điểm không có ràng buộc gì thêm.