题目描述

禾木和乌拉乎在玩游戏。 开始时，有n枚硬币被摆成了一行，从左至右第i枚硬币的价值为a[i]。 游戏的规则是，两人交替从这堆硬币的左侧连续取出若干硬币，然后将取出的硬币的价值累加至自己获得的累计价值中。若对方上次操作取出了$k$枚硬币，那么本次自己最多取出$k×3$枚硬币。当没有硬币可取时，游戏结束。 游戏开始时，由禾木先动手取硬币，最多取出3枚硬币。 请求出当双方都尽可能使自己的累计价值最大的情况下，禾木能获得的累计价值最大是多少。

输入格式

$\\$输入的第一行是一个整数 n，代表硬币的个数。（n<=2000） $\\$第2到第(n+1)行，每行一个整数，第(i+1)行的整数代表第i枚硬币的价值 a[i]。（a[i]<=100000）

输出格式

输出一行一个整数，代表禾木 能获得的最大累计价值。