After meeting up with each other, it's time for Daniel and his friends to rent their skis! Each pair of skis has a specified price as some skis are better quality than others. Together, the group of ~N~ people (including Daniel) are already in line to rent, and no one wants to lose their place. However, after reading the sign on the window, Daniel realizes that there is a special deal—if you choose to rent two pairs of skis together, the cheaper of the two will be at half price (50% off)! While positions in the line can no longer be changed, 2 people can either group together or stay separate.

Can you help Daniel and his friends find the minimum amount of money they need to pay to rent all the skis for the group?

Constraints

For each ~c_i~, ~1 \le c_i \le 10^3~. All ~c_i~ will be even to make calculations easier.

Subtask 1 [10%]

~1 \le N \le 10~

Subtask 2 [90%]

~1 \le N \le 10^6~

Input Specification

The first line will contain the integer ~N~, representing the number of people in the group.

The second line will contain ~N~ space-separated integers ~c_i~, representing the cost of the skis for each person in the group.

Output Specification

Output one integer, representing the minimum cost to rent all the skis in the group.

Sample Input

3
50 20 10

Sample Output

70

Sample Explanation

There are three ways to rent the skis:

~1.~ All people rent separately: ~50 + 20 + 10 = 80~

~2.~ The first two people rent together: ~(50 + 20 * 0.5) + 10 = 70~

~3.~ The last two people rent together: ~50 + (20 + 10 * 0.5) = 75~

The cheapest choice is for the first two people to rent together, so the minimum cost is ~70~.