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 (xem hình).

Input

• Dòng đầu 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 bởi một dấu cách.

Giới hạn:

• ~1 ≤ N ≤ 1000; 1 ≤ a_i ≤ b_i ≤ 1000~.

Output

• 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.

Sample

Input #1

5
2 5
3 8
1 10
7 14
2 5

Output #1

68

Hint

• 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 source: Chuyên Sơn La Online Judge