Walter white , the chemistry teacher turned into a drug manufacturer and dealer tried to crack a deal with the infamous drug dealer Tuco Salamanca .

Walter has different qualities of meth each packed in different packtes.....

The deal was done at rate that if Tuco will buy K packets of meth packets he  will pay the amount which is equal to cost of the most expensive K/2 drugs ( if the K/2 is not an integer consider the upper integer value ) .

Given the price of meth packets , can you tell the least amount that  Walter has to be paid if Tuco buys all of them.

Constraints:
1 <= n <= 10^5
1 <= i<= 10^9

Input Format:

First line contains an integer n.
Next line contains n integers. 
The ith  integer is the price of ith meth packet..

Output Format:

A single integer which is the least cost that has to be paid.

Sample Input:

6
4 5 9 3 6 7

Sample Output:

19

Explanation
Tuco can place as many orders he want containing any amount of packets for the above input ,Tuco will give three orders containing 2 items
4 and 3
5 and 6
7 and 9
the least amount to be paid will be : 4+6+9= 19