In an orchard, D has already collected all the fruit and put them in different piles. Now D wants to combine all the fruit into one pile.

For each "combine" operation, D can combine two piles of fruit into one, using an amount of stamina equal to the total weight of the two piles. We can see that after $n-1$ "combine" operations, there would only be one pile.

Find the minimum amount of stamina that D needs to combine all fruit into one pile.

Input Specification

The first line contains an integer $n$, representing the number of piles of fruit. The second line contains $n$ integers, representing the weight of each pile.

Output Specification

Output the minimum stamina D needs to combine all fruit into one pile.

Sample Input

3
1 2 9

Sample Output

15

Constraints

For $30\mathrm{\%}$ of the data, $n\le 1000$,

For $50\mathrm{\%}$ of the data, $n\le 5000$,

For $100\mathrm{\%}$ of the data, $n\le 10000$.