409307: GYM103483 A Natives

Captain Cook and his team were captured by island natives. Not to be eaten, the adventurers must give some treasures to natives. It turned out that the captain has $$$n$$$ treasures.

Chieftain of the natives agrees to let the captain and his team go, if they give him at least half of his treasures. All treasures look pretty to him, so the chieftain agrees to get any treasures, he only wants to get at least half of them.

But actually each treasure has its own value known to Cook. The value of the $$$i$$$-th treasure is $$$a_i$$$. Help the captain to decide which treasures he should give to the chieftain so that the total value of the treasures he keeps to himself is maximum possible.

The first line of input contains integer $$$n$$$ ($$$2 \le n \le 1000$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 1000$$$).

Output one integer — the maximum possible total value of treasures that the captain can keep for himself after he gives at least half of his treasures to the natives.

6
2 4 1 3 3 5

12

In the given example Cook can give treasures with values $$$1$$$, $$$2$$$ and $$$3$$$ to the chieftain keeping treasures with values $$$3$$$, $$$4$$$ and $$$5$$$ to himself. Their total value is $$$3+4+5=12$$$.