题目描述

Santo刚刚与房东打赌赢得了一间在New Clondike的大客厅。今天，他来到这个大客厅欣赏他的奖品。房东摆出了一行瓶子在酒吧上，瓶子里都装有不同体积的酒，味道也各不相同。

房东规则：

1. 你可以喝尽可能多的酒，但一旦打开必须喝完，喝完放回原处；
2. 必须从左至右依次喝；
3. 不能连续超过三瓶（等价于任意三个连续瓶子中至少有一个不喝）。

请帮助Santo找出他能喝的酒的最大总体积。

时间限制

2000

内存限制

131072

输入格式

第一行一个整数N（N ≤ 700），表示酒瓶数量。 接下来有N行，第I+1行的数字代表酒瓶I中酒的体积。

输出格式

一个数字，表示能喝的酒的最大总体积。

样例输入

6
6
10
13
9
8
1

样例输出

33