Description

In an orchard, Duoduo has already knocked down all the fruits and separated them into different piles by type. Duoduo decides to merge all the fruits into a single pile.

In each merge, Duoduo can combine two piles of fruits, and the effort spent equals the sum of the weights of the two piles. It is clear that after $n-1$ merges, there will be only one pile left. The total effort spent by Duoduo when merging the fruits equals the sum of the efforts of each merge.

Because it also takes a lot of effort to carry these fruits home, Duoduo wants to save as much effort as possible when merging. Assume each fruit has weight $1$, and you are given the number of types of fruits and the count of each type. Your task is to design a merging order that minimizes the total effort and output this minimum effort.

For example, there are $3$ types of fruits, with counts $1$, $2$, and $9$. You can first merge the $1$ and $2$ piles to get a new pile of $3$, costing $3$ effort. Then merge this new pile with the original third pile to get a new pile of $12$, costing $12$ effort. So the total effort equals $=3+12=15$. It can be proven that $15$ is the minimum total effort.

Input Format

Two lines. The first line is an integer $n(1\leq n\leq 10000)$, representing the number of fruit types. The second line contains $n$ integers separated by spaces. The $i$-th integer $a_i(1\leq a_i\leq 20000)$ is the number of fruits of type $i$.

Output Format

A single integer, which is the minimum total effort. The input guarantees that this value is less than $2^{31}$.

3 
1 2 9 

15

Hint

Constraints:

• For $30\%$ of the testdata, $n \le 1000$.
• For $50\%$ of the testdata, $n \le 5000$.
• For all testdata, $n \le 10000$.

Translated by ChatGPT 5