[Usaco2010 Dec]Treasure Chest 藏宝箱

贝西和邦妮找到了一个藏宝箱，里面都是金币！但是身为两头牛，她们不能到商店里把金币换成好吃的东西，于是她们只能用这些金币来玩游戏了。

藏宝箱里一共有 $n$ 枚金币，第 $i$ 枚金币的价值是 $c_i$ 。贝西和邦妮把金币排成一条直线，她们轮流取金币，看谁取到的钱最多。贝西先取，每次只能取一枚金币，而且只能选择取直线两头的金币，不能取走中间的金币。当所有金币取完之后，游戏就结束了。

贝西和邦妮都是非常聪明的，她们会采用最好的办法让自己取到的金币最多。请帮助贝西计算一下，她能拿到多少钱？

输入格式

第一行一个整数 $n$ ，表示金币的数量。

第 $2$ 到第 $n+1$ 行，第 $i+1$ 行一个整数 $c_i$ ，表示第 $i$ 枚金币的价值。

一行一个整数，表示如果双方都按最优策略玩游戏，先手贝西可以拿到的最大价值。

贝西最好的取法是先取 $35$ ，然后邦妮会取 $30$ ，贝西再取 $25$ ，邦妮最后取 $10$ 。贝西共得到 $35+25=60$ 。

本题为 USACO 2010 Dec 试题「Treasure Chest 藏宝箱」，题面与测试数据整理自 BZOJ 2101。