Ban nhạc Keshoku sắp tới sẽ phải biểu diễn ở lễ hội trường, và Nijika cần Bocchi sáng tác một bài hát mới cho nhóm.

Nijika sẽ cho Bocchi \(n\) nốt nhạc, với mỗi nốt \(i\) có hai chỉ số \(a_{i}\) và \(b_{i}\) lần lượt là tần số và độ hay của nốt đó. Một giai điệu là một dãy các nốt nhạc (không nhất thiết phải liên tiếp) được chọn từ \(n\) nốt nhạc đã cho.

• Gọi \(S\) là tổng độ hay của các nốt trong giai điệu, \(A_{\min}\) là tần số nhỏ nhất trong giai điệu và \(A_{\max}\) là tần số lớn nhất trong giai điệu.

• Để một giai điệu được hay thì sự chênh lệch về tần số không nên quá lớn, độ hay của một giai điệu chính là công thức \(S - (A_{\max} - A_{\min})\). Tức là lấy tổng độ hay của tất cả các nốt nhạc trừ đi cho chênh lệch giữa nốt nhạc lớn nhất và nhỏ nhất.

Nhiệm vụ của Bocchi là chọn các nốt nhạc để làm giai điệu sao cho giá trị độ hay của giai điệu đã chọn là lớn nhất.

Input

• Dòng thứ nhất chứa số nguyên \(n\) \((2 \leq n \leq 5 \times 10^{5})\) - số nốt nhạc được cho.
• Dòng thứ \(i\) \((1 \leq i \leq n)\) của \(n\) dòng chứa hai số \(a_{i}\) \((1 \leq a_{i} \leq 10^{15})\), \(b_{i}\) \((1 \leq b_{i} \leq 10^{9})\) .Tức là tần số của nốt \(i\) là \(a_{i}\) và độ hay của nốt \(i\) là \(b_{i}\).

Output

• Một dòng duy nhất là giá trị giai điệu hay nhất mà Bocchi có thể tạo được.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n \leq 16\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 300\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \leq 5000\).
• Subtask \(4\) (\(50\%\) số điểm): Không ràng buộc gì thêm.

Example

3
2 3 
11 2
4 5

6