보물 상자

베시와 보니가 반짝이는 금화로 가득 찬 보물 상자를 발견했습니다. 하지만 소인 두 마리는 금화를 쓰는 대신 금화로 게임을 하기로 했습니다.

$N$개의 금화가 한 줄로 놓여 있고, 왼쪽에서 $i$번째 금화의 값어치는 $C_i$입니다. 베시와 보니는 번갈아 가며 차례를 진행합니다. 각 차례에 소는 줄의 가장 왼쪽 끝 또는 가장 오른쪽 끝에서 금화를 정확히 하나 가져가고, 그 금화의 값어치를 자신의 점수에 더합니다. 금화가 하나도 남지 않으면 게임이 끝납니다.

두 소는 모두 자신이 모은 금화 값어치의 합을 최대로 하려고 최적으로 행동하며, 베시가 먼저 시작합니다. 두 소가 모두 최적으로 행동할 때, 베시가 확보할 수 있는 금화 값어치 합의 최댓값을 구하세요.

첫째 줄에 금화의 개수를 나타내는 정수 $N$이 주어집니다 ($1 \le N \le 5000$).

다음 $N$개의 줄에는 각각 정수 $C_i$가 하나씩 주어지며, 이는 왼쪽에서 $i$번째 금화의 값어치입니다 ($1 \le C_i \le 5000$).

두 소가 모두 최적으로 행동할 때 베시가 모을 수 있는 금화 값어치 합의 최댓값을 정수 하나로 출력하세요.