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í sau:

• 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 giá trị H lớn nhất.

Dữ liệu vào: TL.INP

• Dòng đầu tiên chứa số nguyên N là số lượng các bức tranh, thỏa mãn: ~2 \le N \le 500000~
• Dòng thứ i trong N dòng tiếp theo chứa hai số nguyên Ai và Bi, lần lượt là kích thước và định giá của bức tranh thứ i, thỏa mãn: ~1 \le A_i \le 10^{15}~, ~1 \le B_i \le 10^9~, ~1 \le i \le N~

Kết quả: TL.OUT

Ghi ra số nguyên H lớn nhất tìm được.

Ràng buộc

• Có 25% số test tương ứng 25% số điểm với n ≤ 16.
• Có 25% số test tương ứng 25% số điểm với n ≤ 300.
• Có 25% số test tương ứng 25% số điểm với n ≤ 5000.
• 25% số test còn lại tương ứng 25% số điểm không có ràng buộc gì thêm.

Ví dụ

TL.INP

3
2 3
9 2
4 5

TL.OUT

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.