Giải bài trực tuyến

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ố ai  và bi, độ dài cạnh của hình chữ nhật thứ i.
Ràng buộc : 0 < n < 1000; 0 < ai < bi < 1000, với i = 1, 2 … n. 

Ví dụ:
5 
2 5 
3 8 
1 10 
7 14 
2 5 

OUTPUT

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

Ví dụ: 

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

Problem for kid - Please, think like kid.