You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

In an orchard, Duoduo has picked all the fruits and sorted them into different piles based on their types. Duoduo decides to combine all the fruits into one pile.
Each time, Duoduo can merge two piles of fruits, and the energy 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 remains. The total energy Duoduo consumes during the merging process is equal to the sum of the energy consumed in each merge.
Since Duoduo still needs to exert great effort to carry these fruits home, he wants to save as much energy as possible during the merging process. Assuming each fruit weighs $1$, and given the number of fruit types and the quantity of each type, your task is to design a merging order that minimizes the energy Duoduo consumes and output this minimum energy value.
For example, if there are $3$ types of fruits with quantities of $1$, $2$, and $9$, you can first merge the piles of $1$ and $2$, resulting in a new pile of $3$, consuming $3$ units of energy. Then, merge this new pile with the original third pile, resulting in a new pile of $12$, consuming $12$ units of energy. Therefore, Duoduo's total energy consumption is $3+12=15$. It can be proven that $15$ is the minimum energy consumption.

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 quantity of the $i$-th type of fruit.

Output Format

A single line containing an integer, representing the minimum energy consumption. The input data guarantees this value is less than $2^{31}$.

Sample

3
1 2 9

15