Triển lãm

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 từ tệp văn bản TL.INP:

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

Kết quả ghi ra tệp văn bản TL.OUT: Số nguyên $H$ lớn nhất tìm được.

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