Natives

Interview

Time limit1sMemory limit512 MB

Summary

Given n treasure values, find the largest total the captain can keep after giving at least half of the treasures to the chieftain.

Level: Easy3 of 10
Topics: Greedy, Sorting
Solved: No attempts yet

Problem

Captain Cook and his team were captured by island natives. To avoid being eaten, the adventurers must give some of their treasures to the natives. The captain has $n$ treasures.

The chieftain agrees to let the captain and his team go if they give him at least half of the treasures. The chieftain does not care which treasures he gets, as long as he receives at least half of them.

Each treasure has its own value, known to Cook. The value of the $i$ -th treasure is $a_i$ . Help the captain decide which treasures to give to the chieftain so that the total value of the treasures he keeps is as large as possible.

Input

The first line contains an 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

Print one integer: the maximum total value of the treasures that the captain can keep after giving at least half of his treasures to the natives.

Examples1

Example 1
Input
```
6
2 4 1 3 3 5
```
Expected output
```
12
```