~Molang~ và ~PiuPiu~ vừa săn trên mạng được bộ thẻ bài đấu trí cho ~2~ người chơi, và hôm nay họ quyết định lấy ra để thi tài với nhau. ~Molang~ xếp bài lên bàn thành một dãy ~N~ thẻ bài liên tiếp đánh số từ ~1~ tới ~N~, thẻ bài thứ ~i~ có giá trị là ~a_i~. ~Molang~ sẽ cố gắng thu thập các thẻ bài này, nhưng ở mỗi lượt, ~PiuPiu~ sẽ chọn một ranh giới giữa hai thẻ bài liên tiếp nào đó và chia dãy ra làm hai phần. Lúc này ~Molang~ sẽ chọn ~1~ trong ~2~ dãy và thu thập các lá bài, còn ~PiuPiu~ nhận được số điểm bằng tổng giá trị các lá bài còn lại. Trò chơi sẽ kết thúc khi trên bàn chỉ còn lại ~1~ lá bài.
Biết rằng ~Molang~ muốn ~PiuPiu~ đạt điểm thấp nhất có thể, nhưng với tư duy chiến thuật, ~PiuPiu~ đã tìm ra được cách để bản thân có được số điểm cao nhất. Bạn hãy tính số điểm ấy của ~PiuPiu~.
Dữ liệu
- Dòng thứ nhất chứa số nguyên ~N~ ~(1 \le N \le 2000)~.
- Dòng thứ ~2~ chứa ~N~ số nguyên ~a_i~ ~(1 \le a_i \le 5000)~.
Kết quả
- Gồm một số duy nhất là số điểm lớn nhất mà ~PiuPiu~ có thể đạt được.
Giới hạn
- Subtask ~1~ ~(20\%)~: ~ 1 \le N \le 10~.
- Subtask ~2~ ~(30\%)~: ~ 1 \le N \le 100~.
- Subtask ~3~ ~(50\%)~: ~ 1 \le N \le 2000~.
Ví dụ
Dữ liệu
4
2 4 3 2
Kết quả
7
Giải thích
- Ở lượt đầu, ~PiuPiu~ đặt ranh giới chia dãy thành ~[2, 4]~ và ~[3, 2]~, ~Molang~ thu thập các lá bài ~[2, 4]~ và ~PiuPiu~ nhận được ~5~ điểm.
- Lượt tiếp theo, trên bàn chỉ còn lại hai lá bài ~[3. 2]~, ~PiuPiu~ chia làm hai phần, ~Molang~ thu thập lá mang giá trị ~3~ và ~PiuPiu~ nhận được ~2~ điểm. Không có cách nào đạt được nhiều điểm hơn cho ~PiuPiu~.
Bình luận