Description

In an orchard, Duoduo has picked all the fruits and divided them into different piles based on their types. Duoduo decides to merge all the fruits into a single pile.
Each time two piles are merged, the amount of physical effort consumed is equal to the sum of the weights of the two piles. It can be seen that after n-1 merges, only one pile will remain.
The total physical effort Duoduo consumes when merging the fruits is equal to the sum of the effort consumed in each merge.
Because Duoduo still needs to exert great effort to carry the fruits home, it is essential to minimize the physical effort during the merging process.
Assume each fruit weighs 1 unit, and given the number of fruit types and the count of each type, your task is to design a merging sequence that minimizes Duoduo's physical effort and output this minimum value.
For example, if there are 3 types of fruits with counts of 1, 2, and 9 respectively, you can first merge the piles of 1 and 2. The new pile will have a count of 3, consuming 3 units of effort. Then, merge the new pile with the original third pile (count 9), resulting in a new pile of 12, consuming 12 units of effort. Thus, the total effort consumed by Duoduo is 3 + 12 = 15. It can be proven that 15 is the minimum possible effort.

Input Format

Two lines:
The first line contains an integer n (1 ≤ n ≤ 30000), representing the number of fruit types.
The second line contains n integers separated by spaces, where the i-th integer $a_i$ (1 ≤ $a_i$ ≤ 20000) represents the count of the i-th type of fruit.

Output Format

A single line containing one integer, which is the minimum physical effort value. The input data guarantees this value is less than $2^{31}$.

3
1 2 9

15

10
3 5 1 7 6 4 2 5 4 1

120