Coin Game

Two players take turns in a coin game.

Initially $N$ coins are stacked in a single pile. The $i$-th coin from the top has value $C_i$.

The first player takes one or two coins from the top of the pile. On every turn after that, a player may take at most twice as many coins as the previous player just took, and must take at least one. In other words, if the previous player took $k$ coins, the current player may take from $1$ up to $2k$ coins from the top. (If fewer coins remain, they take only what is left.) The game ends when no coins remain.

Both players act optimally to maximize the total value of the coins they collect. Assuming the second player also plays to maximize their own total, find the maximum total value the first player can collect.

The first line contains the number of coins $N$ ($5 \le N \le 2000$).

Each of the next $N$ lines contains $C_i$, the value of the $i$-th coin from the top ($1 \le C_i \le 100000$).

Print the maximum total value the first player can collect.

Consider coins whose values from top to bottom are $1, 3, 1, 7, 2$.

The first player takes one coin (value $1$). The second player also takes one coin (value $3$). The first player then takes two coins (values $1, 7$, total $9$). Finally the second player takes the remaining coin (value $2$, total $5$). The first player's collected value of $9$ is the maximum.