In an orchard, Dodo had already knocked down all the fruits, and divided them into different piles according to the different types of fruits. Dodo decided to combine all the fruits into one pile. Every time you merge, Dodo can merge two piles of fruits together, and the energy consumed is equal to the sum of the weight of the two piles of fruits. It can be said that after all the fruits are merged n-1 times, there is only one pile left. The total stamina consumed by Dodo when merging the fruits is equal to the sum of the stamina consumed for each merge.

Because it will take great effort to move these fruits home, Dodo should save as much energy as possible when merging the fruits. Assuming that the weight of each fruit is 1, and the number of fruit types and the number of each fruit are known, your task is to design a combined sequence plan to minimize the amount of physical effort that Dodo consumes, and output the minimum value of energy spent.

For example, there are 3 kinds of fruits, the numbers are 1, 2, and 9. You can merge piles 1 and 2 first, the number of the new pile is 3, and the energy spent is 3. Then, merge the new pile with the original third pile, and get a new pile, the number is 12, and the physical effort is 12. So Dodo consumes a total of physical energy: 3 + 12 = 15. We have proven that 15 is the minimum physical expenditure value.

The input file fruit.in consists of two lines. The first line is an integer n (1 <= n <= 10000), which represents the number of fruit types. The second line contains n integers, separated by spaces. The i-th integer a_i (1 <= a_i <= 20000) is the number of the i-th fruit.

The output file fruit.out includes one line, which contains only an integer, is the minimum physical exertion value. The input number ensures that this value is less than 231.