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})$. Hai tiêu chí cuối được gộp vào công thức này: cần chọn một tập khác rỗng các bức tranh sao cho $H$ lớn nhất. Nếu chỉ trưng bày một bức tranh thì $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

In ra số nguyên $H$ lớn nhất 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$.

Subtasks

• $25\%$ số test ứng với $25\%$ số điểm có $N\le 16$.
• $25\%$ số test ứng với $25\%$ số điểm có $N\le 300$.
• $25\%$ số test ứng với $25\%$ số điểm có $N\le 5000$.
• $25\%$ số test còn lại ứng với $25\%$ số điểm không có ràng buộc gì thêm.

Điểm được tính theo từng test.

Ví dụ