[Usaco2009 Nov]硬币游戏

农夫约翰的奶牛喜欢玩硬币游戏，因此他发明了一种称为「Xoinc」的两人硬币游戏。

初始时，一个有 $n$ 枚硬币的堆栈放在地上，从堆顶数起的第 $i$ 枚硬币的币值为 $c_i$ 。

开始玩游戏时，第一个玩家可以从堆顶拿走一枚或两枚硬币。如果第一个玩家只拿走堆顶的一枚硬币，那么第二个玩家可以拿走随后的一枚或两枚硬币；如果第一个玩家拿走两枚硬币，则第二个玩家可以拿走 $1, 2, 3$ 或 $4$ 枚硬币。

在每一轮中，当前的玩家至少拿走一枚硬币，至多拿走对手上一次所拿硬币数量的两倍。当没有硬币可拿时，游戏结束。

两个玩家都希望拿到最多钱数的硬币。请问，当游戏结束时，第一个玩家最多能拿多少钱呢？

输入格式

第一行一个整数 $n$ 。

第 $2$ 到第 $n+1$ 行，第 $i+1$ 行包含一个整数 $c_i$ 。

一行一个整数，表示第一个玩家能拿走的最大钱数。

第 $1$ 个玩家先取走第 $1$ 枚，第 $2$ 个玩家取第 $2$ 枚；第 $1$ 个玩家取走第 $3, 4$ 两枚，第 $2$ 个玩家取走最后 $1$ 枚。第 $1$ 个玩家共得到 $1+1+7=9$ 。

本题为 USACO 2009 Nov 试题「硬币游戏」，题面与测试数据整理自 BZOJ 2017。