Đường gấp khúc trên các hình chữ nhật

Trên trục hoành \(Ox\) đặt \(n\) hình chữ nhật đứng sát nhau từ trái sang phải theo thứ tự chỉ số \(1, 2, \dots, n\). Hình chữ nhật thứ \(i\) có hai kích thước \(a_i\) và \(b_i\); ta được tự chọn cạnh nào nằm trên trục \(Ox\) (cạnh đó là chiều rộng \(w_i\), cạnh còn lại là chiều cao \(h_i\)). Việc chọn được thực hiện độc lập cho từng hình.

Xét đường gấp khúc chạy dọc phía trên chuỗi hình chữ nhật, xuất phát từ đỉnh trên trái của hình thứ nhất và kết thúc ở đỉnh trên phải của hình thứ \(n\): nó đi ngang theo cạnh trên của từng hình (dài \(w_i\)) và, tại chỗ hai hình kề nhau \(i\) và \(i+1\), đi thẳng đứng một đoạn dài \(|h_i - h_{i+1}|\) để chuyển sang cạnh trên của hình tiếp theo. Độ dài của đường gấp khúc là

Hãy chọn cách đặt các hình chữ nhật để độ dài đường gấp khúc lớn nhất và in ra giá trị đó.

Input

• Dòng đầu tiên chứa số nguyên \(n\).
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(a_i\) và \(b_i\).

Output

In ra độ dài lớn nhất của đường gấp khúc.

Constraints

• \(1 \le n \le 10^4\)
• \(1 \le a_i, b_i \le 10^9\)

Sample Input

4
3 6
5 2
4 4
1 7

Sample Output

28

Explanation

Chọn chiều cao lần lượt là \(3, 2, 4, 1\) (chiều rộng \(6, 5, 4, 7\)): tổng chiều rộng \(22\), tổng chênh lệch chiều cao \(1 + 2 + 3 = 6\), độ dài \(28\).