동전 게임

두 사람이 번갈아 가며 진행하는 동전 게임이 있다.

처음에 $N$개의 동전이 하나의 더미로 쌓여 있다. 위에서부터 $i$번째 동전의 가치는 $C_i$이다.

첫 번째 사람은 더미의 맨 위에서 동전을 한 개 또는 두 개 가져간다. 그다음부터는 각 차례마다 직전 사람이 가져간 동전 개수의 두 배까지 가져갈 수 있으며, 최소한 한 개는 반드시 가져가야 한다. 즉 직전 사람이 $k$개를 가져갔다면 이번 사람은 맨 위에서 $1$개부터 $2k$개까지 가져갈 수 있다. (남은 동전이 그보다 적다면 남은 것만큼만 가져간다.) 더 이상 가져갈 동전이 없으면 게임이 끝난다.

두 사람 모두 자신이 모은 동전 가치의 합을 최대로 만들려고 최적으로 행동한다. 두 번째 사람도 자신의 이득을 최대화하도록 움직인다고 할 때, 첫 번째 사람이 모을 수 있는 동전 가치 합의 최댓값을 구하여라.

첫째 줄에 동전의 개수 $N$이 주어진다. ($5 \le N \le 2000$)

둘째 줄부터 $N+1$번째 줄까지 각 줄에 맨 위에서부터 $i$번째 동전의 가치 $C_i$가 주어진다. ($1 \le C_i \le 100000$)

첫째 줄에 첫 번째 사람이 모을 수 있는 동전 가치 합의 최댓값을 출력한다.

동전의 가치가 위에서부터 차례로 $1, 3, 1, 7, 2$인 경우를 살펴보자.

첫 번째 사람이 동전 한 개를 가져간다(가치 $1$). 두 번째 사람도 한 개를 가져간다(가치 $3$). 다시 첫 번째 사람이 두 개를 가져간다(가치 $1, 7$, 합 $9$). 마지막으로 두 번째 사람이 남은 동전을 가져간다(가치 $2$, 합 $5$). 이때 첫 번째 사람이 모은 값 $9$가 최댓값이다.