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\ \leq \ i\ \leq \ 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 nhậ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

\[\mathbf{H\ = \ S\ –\ (}\mathbf{a}_{\mathbf{\max}}\mathbf{\ –\ }\mathbf{a}_{\mathbf{\min}}\mathbf{)}\]

Yêu cầu: Hãy giúp giám đốc bảo tàng tìm \(\mathbf{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 bức tranh \((2 \leq n \leq 500\ 000)\)

+ 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 \leq a_{i} \leq 10^{15},\ 1 \leq b_{i} \leq 10^{9},\ 1 \leq i \leq n)\).

Kết quả: ghi số nguyên \(H\) tìm được.

Ràng buộc:

• 25% số test có \(n\ \leq \ 16\).

• 25% số test có \(n\ \leq \ 300\).

• 25% số test có \(n\ \leq \ 5000\).

• 25% số test không có ràng buộc gì thêm

Ví dụ: