Phú ông ở làng AMK rất giàu có, ông có rất nhiều đất đai và nhiều khu rừng gỗ trồng lâu năm rất giá trị. Đặc biệt, ông có khu rừng gỗ Xoan gồm ~N (1 ≤ N ≤ 10^5)~ cây được trồng thẳng hàng trong thời gian chờ khai thác. Phú ông đã nhờ chuyên gia về gỗ định giá trị cho từng cây. Cho dãy gồm ~N~ phần tử ~a_1,a_2,...,a_N~ ~(1 ≤ a_i ≤ 10^6)~ tương ứng là giá trị của cây gỗ thứ ~i~ trong khu rừng mà phú ông đã định giá. Phú ông có hai cô con gái, phú ông dự định cho hai cô con gái của mình khai thác rừng gỗ để làm vốn riêng.
Vì yêu thương con gái út của mình hơn nên phú ông muốn cô khai thác được tổng giá trị gỗ cao nhất. Ông đã đưa ra một cách khai thác như sau: Bắt đầu, cô gái út đã chọn ~X~ ~(1 ≤ X ≤ 3)~ cây gỗ đầu tiên để khai thác. Cô chị chọn ~X~ cây gỗ liên tiếp tiếp theo (chú ý ở mỗi lượt lựa chọn, cô út chọn ~X~ cây thì cô chị phải chọn ~X~ cây tiếp theo, trừ khi số cây còn lại bé hơn ~X~, mỗi lượt lựa chọn cô út có thể thay đổi giá trị ~X~ trong phạm vi đã cho, phải chọn theo thứ tự từ đầu khu rừng đến cuối khu rừng). Việc này cứ tiếp tục cho đến khi khai thác hết rừng.
Yêu cầu: Hãy đưa ra giá trị gỗ lớn nhất mà cô gái út có thể khai thác được thỏa mãn yêu cầu của bài toán.
Dữ liệu vào
- Dòng đầu ghi số nguyên dương ~N~ là số cây Xoan trong khu rừng.
- Dòng thứ hai ghi ~N~ số nguyên dương ~a_1,a_2,...,a_N~ tương ứng là giá trị của từng cây gỗ trong khu rừng. Các số trên một dòng cách nhau bởi một khoảng trắng.
Dữ liệu ra
- Một số nguyên dương duy nhất là tổng giá trị gỗ lớn nhất mà cô út có thể khai thác được.
Sample Input
4
5 4 3 2
Sample Output
12
Giải thích ví dụ: Cô út chọn ~3~ cây đầu tiên, cô chị chọn cây cuối cùng.
Bình luận