땅 두 배로 따먹기

산지니와 현기는 땅을 두 배로 늘려 가며 먹는 게임을 한다. 두 플레이어가 번갈아 턴을 진행하며, 규칙은 다음과 같다.

• 게임을 시작하기 전에 크기가 서로 다른 땅 여러 개가 주어진다. 아직 누구도 먹지 않은 상태이다.
• 각 플레이어는 자신의 턴마다 아래 두 행동 중 하나를 골라 수행한다. 단, 2번 행동은 게임 중 플레이어마다 한 번만 수행할 수 있다.
  1. 아직 먹히지 않은 땅 중 하나를 골라 먹어 자신의 땅으로 만든다.
  2. 아직 먹히지 않은 땅이 둘 이상 있을 경우, 그중 두 개를 골라 먹어 자신의 땅으로 만든다. 그 뒤 자신이 가진 모든 땅의 크기를 두 배로 만든다.
• 먹을 땅이 더 이상 없으면 게임이 끝난다. 먹은 땅의 크기 합이 더 큰 플레이어가 이긴다.

게임 이해도에 자신이 있던 현기는 산지니에게 첫 턴을 양보했다. 산지니는 어떤 상황에서도 이기는 필승법을 찾지 못했지만, 자신이 먹을 땅의 크기 합을 최대로 하여 승률을 높이려 한다. 현기도 같은 전략을 쓴다. 두 플레이어는 승패와 관계없이 자신의 땅 크기를 최대로 만드는 행동을 항상 선택한다. 같은 최댓값을 만드는 방법이 여러 가지라면, 그 플레이어는 상대방 땅의 크기를 가능한 한 작게 만든다. 두 플레이어는 서로의 전략을 알고 있다. 산지니가 먹을 땅의 크기를 구하라.

첫째 줄에 땅의 개수 $N$이 주어진다. ($2 \le N \le 4\,000$)

둘째 줄부터 $N$개의 줄에 걸쳐 정수 $a_i$가 주어진다. $a_i$는 $i+1$번째 줄에 주어진 땅의 크기이다. ($1 \le i \le N$, $1 \le a_i \le 10\,000$)

첫째 줄에 산지니가 먹을 땅의 크기를 출력하라.