25581번 - 땅 두 배로 따먹기

산지니와 현기는 땅 두 배로 따먹기 게임을 진행한다. 땅 두 배로 따먹기 게임은 두 플레이어가 진행하며 자세한 진행 방법은 아래와 같다.

• 게임을 시작하기 전에 아직 누구도 먹지 않은 여러 크기의 땅이 주어진다.
• 각 플레이어는 턴을 번갈아 가며 진행하며, 각자의 턴에 아래의 두 행동 중 하나를 선택하여 수행한다. 단, 2번 행동은 게임 중 플레이어마다 단 한 번만 수행할 수 있다.
  1. 아직 먹히지 않은 땅 중 하나를 골라 먹어 자신의 땅으로 만든다.
  2. 아직 먹히지 않은 땅이 둘 이상 있을 경우 그중 두 개를 골라 먹어 자신의 땅으로 만든다. 그 후, 모든 자신 땅의 크기를 두 배로 만든다.
• 더 이상 먹을 땅이 없을 경우 게임을 종료하고 먹은 땅의 크기가 더 큰 플레이어가 승리한다.

이 게임을 고안한 현기는 이 게임에 대한 이해도가 높다고 자만하여 산지니에게 첫 턴을 양보하였다. 자존심이 상한 산지니는 어느 상황에서도 승리하는 필승법을 생각해내지는 못했지만, 본인이 먹을 땅의 크기를 최대로 하여 승률을 높이고자 한다. 현기 역시 본인이 먹을 땅의 크기를 최대로 하는 전략을 똑같이 사용하여 산지니의 자존심을 무너뜨리려 한다. 즉, 현기와 산지니 모두 게임의 승패와 관계없이 자신이 먹을 땅의 크기를 최대로 하는 데에 최선의 행동을 한다. 각 플레이어가 본인 땅의 크기를 최대로 만드는 방법이 여러 가지일 경우에는 상대방 땅의 크기를 가능한 한 작게 만든다. 현기와 산지니는 상대방의 전략을 서로 알고 있다고 할 때, 산지니가 먹을 땅의 크기를 구하여라.

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

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

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