Tourist stumbles upon some money on the ground while he is travelling. He is hesitant on whether he should pick all of them up, as he is a bit broke after buying too many segment trees. Although he has always been greedy as a CP programmer, he decides to refrain himself a bit this time.
He sees $N$ notes on the floor. Not being too greedy this time, tourist cannot pick up more than half of the notes. What is the maximum total value of the notes he can pick up?

Input

The first line consists of one integer, $N$.
The second line consists of $N$ integers, the value $v_i$ of the notes.

Output

Output an integer, the maximum total value of the notes he can pick up.

Constraints

For all testcases: $1 \le N \le 10^6$, $1 \le v_i \le 10^9$
Subtask 1 (30%): $N \le 10^3$, $v_i \le 10^5$
Subtask 2 (70%): No other constraints