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ứ \(i\) có kích thước là \(A_i\) và được định giá là \(B_i\) \((1 \le i \le 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.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(N\) là số lượng các bức tranh \((2 \le N \le 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 \le A_i \le 10^{15}, 1 \le B_i \le 10^9, 1 \le i \le N)\)

Dữ liệu ra

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

Ràng buộc

• 25% số test có \(n \le 16\)
• 25% số test có \(n \le 300\)
• 25% số test có \(n \le 5000\)
• 25% số test còn lại không ràng buộc gì thêm

Input

3
2 3
9 2
4 5

Output

6

Giải thích

Chọn các bức tranh là 1 và 3 thì H = (3+5)-(4-2)=6 là lớn nhất.