XOINC - A Coin Game

``` ## 题目描述 FJ的奶牛们很喜欢玩硬币游戏，所以FJ给她们发明了一个新的双人硬币游戏：xoinc。 一开始地上有一个由$N(5 \le N\le2000)$个硬币组成的栈，从栈顶数起的第$i$枚硬币有自己的价值$C_i(1\le C_i\le100000)$。 在游戏开始时，先手玩家可以从栈顶拿$1$或$2$枚硬币。如果先手玩家只拿走了$1$枚，那么后手玩家就在接下来拿走$1$或$2$枚；如果先手玩家拿走了$2$枚，那么后手玩家就在接下来拿走$1$到$4$枚。也就是说，除了第一回合，每一回合的玩家都必须拿走至少$1$枚，至多自己的对手在上回合拿走的数目的两倍的硬币数。当栈中的硬币全部被拿走，游戏结束。 在这之后，牛们可以拿她们拿到的硬币向FJ~~交♂易~~买东西，所以游戏目标自然是让自己拿到的硬币的价值尽量大。假设后手玩家采取了最好的决策，那么先手玩家能拿到的最大的硬币价值是多少？ ## 输入格式 第一行一个整数$N$，接下来$N$行每行一个整数$C_i$。 ## 输出格式 一行一个整数，双方都采取最佳策略时先手拿到的硬币价值。 样例不放了…… ## 样例解释： 先手先拿走第一个硬币，价值为1，然后后手也拿走一个价值为3的硬币，先手再拿走两个硬币，价值为1和7，总价值为1+1+7=9。然后后手拿走剩下的一枚硬币。 ```

Farmer John's cows like to play coin games so FJ has invented with a new two-player coin game called Xoinc for them. Initially a stack of N (5 <= N <= 2,000) coins sits on the ground; coin i from the top has integer value C\_i (1 <= C\_i <= 100,000). The first player starts the game by taking the top one or two coins (C\_1 and maybe C\_2) from the stack. If the first player takes just the top coin, the second player may take the following one or two coins in the next turn. If the first player takes two coins then the second player may take the top one, two, three or four coins from the stack. In each turn, the current player must take at least one coin and at most two times the amount of coins last taken by the opposing player. The game is over when there are no more coins to take. Afterwards, they can use the value of the coins they have taken from the stack to buy treats from FJ, so naturally, their purpose in the game is to maximize the total value of the coins they take. Assuming the second player plays optimally to maximize his own winnings, what is the highest total value that the first player can have when the game is over? **Input** Line 1: A single integer: N Lines 2..N+1: Line i+1 contains a single integer: C\_i **Output** A single integer representing the maximum value that can be made by the first player. **Example** **Input:** 5 1 3 1 7 2 **Output:** 9 **Explanation:** The first player starts by taking a single coin (value 1). The opponent takes one coin as well (value 3). The first player takes two more coins (values 1 and 7 -- total 9). The second player gets the leftover coin (value 2-- total 5).