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\%~ of the data, ~n \le 1\,000~,

For ~50\%~ of the data, ~n \le 5\,000~,

For ~100\%~ of the data, ~n \le 10\,000~.