Buy One, Get One Free

Description:

Input:

Input will begin with an integer n (1 ≤ n ≤ 500000), the number of pies you wish to acquire. Following this is a line with n integers, each indicating the cost of a pie. All costs are positive integers not exceeding 10⁹.

Output:

Print the minimum cost to acquire all the pies.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Sample Input:

6
3 4 5 3 4 5

Sample Output:

14

Sample Input:

5
5 5 5 5 5

Sample Output:

25

Sample Input:

4
309999 6000 2080 2080

Sample Output:

314159

Note:

In the first test case you can pay for a pie with cost 5 and get a pie with cost 4 for free, then pay for a pie with cost 5 and get a pie with cost 3 for free, then pay for a pie with cost 4 and get a pie with cost 3 for free.

In the second test case you have to pay full price for every pie.