#431. DPRECLINE – Độ dài đường gấp khúc

Cho hình chữ nhật đánh số từ đến , các hình chữ nhật này được đặt tiếp xúc với trục 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 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).

Dữ liệu vào:

• Dòng đầu ghi số nguyên dương ;
• dòng tiếp theo, dòng thứ chứa hai số nguyên dương 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.

Dữ liệu 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 , và . Độ dài của đoạn này là

Giới hạn:

• .