Doubling Land Grab

Sanjini and Hyeongi play a land doubling game. Two players take turns, and the rules are as follows.

• Before the game starts, several plots of land with various sizes are given. No one has taken any of them yet.
• On each turn, a player chooses one of the two actions below and performs it. However, action 2 can be performed only once per player during the game.
  1. Take one of the plots that has not been taken yet and make it your own.
  2. If two or more untaken plots remain, take two of them and make them your own. Then double the size of all plots you own.
• When no untaken plots remain, the game ends. The player whose taken land has the larger total size wins.

Hyeongi, who is overconfident about his understanding of the game, gave the first turn to Sanjini. Sanjini did not find a winning strategy that works in every situation, but he wants to raise his chances by making the total size of the land he takes as large as possible. Hyeongi uses the same strategy. Both players always choose the action that maximizes the size of their own land, whether or not it wins. If several ways give the same maximum for a player, that player makes the opponent's land as small as possible. Both players know each other's strategy. Find the size of the land Sanjini takes.

The first line contains the number of plots $N$. ($2 \le N \le 4\,000$)

Each of the next $N$ lines contains an integer $a_i$, the size of the plot given on line $i+1$. ($1 \le i \le N$, $1 \le a_i \le 10\,000$)

Print the size of the land Sanjini takes.