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

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản

Đề bài

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

Dữ liệu vào:

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

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

Giới hạn:

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