파머 존스의 소들은 동전 게임 하는 것을 좋아해서 파머 존스는 소들을 위해 두 명에서 할 수 있는 Xoinc라는 동전 게임을 만들었다.

처음에 N개의 코인이 바닥에 쌓여있다. (꼭대기에서 i번째에 있는 동전의 가치는 C_i이다)

첫 번째 사람은 꼭대기에서 한 개 혹은 두 개의 동전을 가져간다. 만일 첫 번째 사람이 꼭대기에 있는 동전만 가져갔을 경우, 두 번째 사람은 한 개 또는 두 개의 동전만 가져갈 수 있다. 만일 첫 번째 사람이 두 개의 동전을 가져갔을 경우, 두 번째 선수는 한 개부터 네 개의 동전을 가져갈 수 있다. 각각의 턴마다, 동전을 가져가는 사람은 최소 한 개부터 전 사람이 가져간 동전의 두 배까지 가져갈 수 있다. 더 이상 가져갈 동전이 없다면 게임이 끝난다.

이후에, 게임에서 얻은 동전으로 파머 존스에게서 물건을 살 수 있다. 그러므로, 그들은 최대한 많은 돈을 가져가야 한다. 두 번째 사람이 게임에서 돈을 최대로 얻기 위해 최적의 상황으로 돈을 가져간다고 가정한다면, 게임이 끝났을 때 첫 번째 사람이 가져갈 수 있는 돈의 최댓값을 구하는 프로그램을 작성하라.

입력 형식

첫 번째 줄에는 동전의 개수 N이 주어진다. (5 <= N <= 2,000)

두 번째 줄부터 N+1 번째 줄까지는 C_i가 주어진다. (1 <= C_i <= 100,000)

출력 형식

첫 번째 줄에 첫 번째 사람이 가져갈 수 있는 돈의 최댓값을 출력한다.

예제 입력

5
1
3
1
7
2

예제 출력

9

힌트

1, 3, 1, 7, 2의 가치가 있는 동전이 있다.

첫 번째 사람은 동전 한 개를 가져간다 (가치 : 1). 상대편은 똑같이 한 개를 가져간다 (가치 : 3). 다시 첫 번째 사람은 두 개의 동전을 가져간다 (가치 : 1,7 -- 합계 : 9). 마지막으로 상대편은 남은 동전을 가져간다 (가치 : 2 -- 합계 : 5).