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\).

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})\).

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.
• 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\).

Dữ liệu ra

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

Ràng buộc

• \(2 \le N \le 500000\)
• \(1 \le A_i \le 10^{15}\)
• \(1 \le B_i \le 10^9\)
• \(1 \le i \le N\)
• Có \(25\%\) số test tương ứng \(25\%\) số điểm có \(n \le 16\).
• \(25\%\) số test tương ứng \(25\%\) số điểm có \(n \le 300\).
• \(25\%\) số test tương ứng \(25\%\) số điểm có \(n \le 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ụ