题目描述

农夫约翰的奶牛喜欢玩硬币游戏，因此他发明了一种称为「Xoinc」的两人硬币游戏。初始时，一个有 $n$ 枚硬币的堆栈放在地上，从堆顶数起的第 $i$ 枚硬币的币值为 $c_i$。开始玩游戏时，第一个玩家可以从堆顶拿走一枚或两枚硬币。如果第一个玩家只拿走堆顶的一枚硬币，那么第二个玩家可以拿走随后的一枚或两枚硬币。如果第一个玩家拿走两枚硬币，则第二个玩家可以拿走 $1$，$2$，$3$ 或 $4$ 枚硬币。在每一轮中，当前的玩家至少拿走一枚硬币，至多拿走对手上一次所拿硬币数量的两倍。当没有硬币可拿时，游戏结束。两个玩家都希望拿到最多钱数的硬币。请问，当游戏结束时，第一个玩家最多能拿多少钱呢？

输入格式

第一行：$1$ 个整数 $n$。

第二行到第 $n+1$ 行：第 $i+1$ 行包含 $1$ 个整数 $c_i$。

输出格式

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

5
1
3
1
7
2

9

样例说明 1

第一个玩家先取走第一枚，第二个玩家取第二枚；第一个玩家取走第三、四两枚，第二个玩家取走最后一枚。

数据规模与约定

对于 $100\%$ 的数据，$5 \leq n \leq 2\times10^3$，$1 \leq c_i \leq 10^5$。

题目来源

Silver