Cho ~n~ hình chữ nhật đánh số từ ~1~ đến ~n~, các hình chữ nhật này được đặt tiếp xúc với trục ~Ox~ và nằm kề nhau từ trái qua phải theo thứ tự chỉ số. Mỗi hình chữ nhật có thể tiếp xúc với trục ~Ox~ theo bất kỳ cạnh nào. Cần tính độ dài lớn nhất của đường gấp phía trên.

Dữ liệu vào

• Dòng đầu tiên ghi số nguyên dương ~n~
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~a_i,b_i~ lần lượt là chiều rộng và chiều dài của hình chữ nhật, hai số cách nhau một dấu cách.

Kết quả ra

• Một số nguyên duy nhất là độ dài lớn nhất của đường gấp khúc phía trên

Ví dụ

Dữ liệu vào

5
2 5
3 8
1 10
7 14
2 5

Dữ liệu ra

68

Giải thích

• cách xếp mà thu được chiều dài lớn nhất là hình trên. Cạnh phía trên gồm các đoạn ~DC,CG,GF,FJ,JI,IM,ML,LP,PO~.Độ dài của đoạn là ~5+6+3+7+10+13+7+12+5=68~

Giới hạn

• ~1 \le N \le 10^6 ; 1 \le a_i \le b_i \le 10^5 ~