最初地面上有一堆n个硬币(5< =n< =2000)，从上面数第i个硬币的价值为C_i(1< =C_i< =100000); 游戏开始后，A先取一枚或两枚硬币。如果A取了一枚，那么B可以继续取一枚或两枚；如果A取了两枚，那么B可以取一到四枚硬币。每次都只能从最上面取。每一次，当前取硬币的人都至少取一枚硬币，最多可以取他的对手上一次取硬币数目的两倍。当没有硬币可取的时候，游戏就结束了。 然后，他们就可以用得到的硬币向John买东西，当然，他们游戏的目的就是要尽可能使自己得到的硬币价值更大。现在你的任务是，求出在两个人都想得到更大价值的情况下，游戏结束后，第一个人最多能得到的硬币价值。

第1行：  一个整数，N（5< =N< =2000）。  第2到n+1行：  第  i+1  行代表从上数第i枚硬币的价值。

一行：一个数字，第一个人能得到的最大价值

5
1
3
1
7
2

9

usaco&nbsp nov09&nbsp Ag&nbsp  translated&nbsp by&nbsp pricez