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 cạnh (xem hình). Cần tính độ dài lớn nhất của đường gấp phía trên (xem hình)

Input

Dòng đầu tiên ghi số hình chữ nhật ~n~, ~n~ dòng tiếp theo mỗi dòng ghi hai số ~a_i~ và ~b_i~, độ dài cạnh của hình chữ nhật thứ ~i~.

Output

Ghi ra độ dài lớn nhất tìm được.

Giới hạn

~0 < n < 1000~;

~0 < a_i < b_i < 1000~, với ~i = 1~, ~2~, ..., ~n~.

Sample Input

5 
2 5 
3 8 
1 10 
7 14 
2 5

Sample Output

68

Note

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~, và ~PO~.

Độ dài của đoạn này là ~5 + 6 + 3 + 7 + 10 + 13 + 7 + 12 + 5 = 68~

Problem for kid - Please, think like kid.