#1315. STATUES - Bán tượng

Bờm phát hiện một hang ngầm chứa bức tượng cổ. Các bức tượng cổ khá lớn nên chỉ có thể lấy ra lần lượt từ hai cửa hang ngầm ở hai đầu. Theo đánh giá của các chuyên gia, bức tượng thứ từ trái sang có giá trị .

Bờm rao bán bức tượng theo quy cách: mỗi lần bán một bức tượng (lấy ra từ một trong hai đầu của hang ngầm), bức tượng thứ nếu bán ở lượt thứ sẽ có giá .

Hãy xác định tổng thu lớn nhất nếu Bờm bán bức tượng theo cách tối ưu.

Dữ liệu vào:

• Dòng đầu chứa số nguyên ;
• dòng tiếp theo chứa số nguyên .

Dữ liệu ra:

• Một số nguyên là tổng thu lớn nhất.

Ví dụ:

Dữ liệu vào:

5
1
3
1
5
2

Dữ liệu ra:

43