Bạn là một chỉ huy cho một tiểu đội thuộc lực lượng đặc nhiệm Hoa Kỳ đang làm nhiệm vụ tại Afghanistan. Trong một lần đi làm nhiệm vụ, bạn bị phục kích bởi một lượng lớn phiến quân Taliban, mặc dù đã ra sức bắn trả nhưng hoả lực của kẻ thù là rất lớn. Trong tình huống đó bạn đã quyết định gọi sự hỗ trợ từ không quân. Ngay lập tức, căn cứ đã cử đi chiếc phi cơ ném bom AC-130 để giúp đỡ, tuy nhiên, việc phải bắn trả từ trên cao là rất khó và số lượng đạn dược hiện tại là không nhiều nên bạn cần phải định vị vị trí của quân địch cho phi công.

Được biết hiện tại có ~N~ quân địch ở các vị trí ~(x, y)~ trên bản đồ. Bạn cần phải tìm một tập hợp S không rỗng gồm các vị trí ~i~ là các địa điểm để tấn công. Độ hiệu quả của một chiến dịch tấn công được tính bằng giá trị ~F~ = ~\sum_{i \in S}y_i - (max(x_i) - min(x_i))~. Hãy tìm chiến dịch tấn công có độ hiệu quả lớn nhất để giúp các đồng đội và bảo toàn cái mạng nhỏ của bạn quay về.

Input

• Dòng đầu tiên gồm số ~N~ là số lượng phiến quân Taliban ~(2 \le N \le 5 \times 10^5)~

• ~N~ dòng sau mỗi dòng gồm ~2~ số ~x_i~, ~y_i~ chỉ toạ độ của tên lính thứ ~i~ ~(1 \le x_i \le 10^{15}, 1 \le y_i \le 10^9)~

Output

• Một số nguyên duy nhất là độ hiệu quả ~F~ lớn nhất của chiến dịch tấn công tìm được.

Subtask

• ~10\%~ số test đầu tiên có ~N \le 20~

• ~20\%~ số test tiếp theo có ~N \le 300~

• ~20\%~ số test tiếp theo có ~N \le 5000~

• ~50\%~ số test còn lại không có điều kiện gì thêm.

Sample Input 1

3
2 3
10 2
4 5

Sample Output 1

6

Note

• Chọn điểm ~1~ và ~3~ để có ~(3 + 5) - (4 - 2) = 6~.