Merging Fruits

Problem Description

In an orchard, Duoduo has already picked all the fruits and sorted them into different piles by type. Duoduo decides to merge all the fruits into one pile.

Each time, Duoduo can merge two piles of fruit together; the physical effort consumed equals the sum of the weights of the two piles. It can be seen that after $n-1$ merges, only one pile remains. The total physical effort Duoduo consumes while merging equals the sum of the effort consumed in each merge.

Since Duoduo also has to spend great effort carrying these fruits home, Duoduo wants to save as much effort as possible when merging the fruits. 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 Duoduo's physical effort, and output this minimum effort.

For example, with $3$ types of fruit, with quantities $1$, $2$, $9$ respectively: we can first merge piles $1$ and $2$, producing a new pile of size $3$ and consuming $3$ effort; then merge this new pile with the original third pile, producing a new pile of size $12$ and consuming $12$ effort. So Duoduo consumes a total of $3+12=15$ effort. It can be proven that $15$ is the minimum possible effort.

Input Format

Two lines in total. The first line is an integer $n\;(1 \le n \le 10000)$, the number of fruit types. The second line contains $n$ integers separated by spaces, where the $i$-th integer $a_i\;(1 \le a_i \le 20000)$ is the quantity of the $i$-th type of fruit.

Output Format

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

Sample Input

3
1 2 9

Sample Output

15

Hint

For $30\%$ of the data, $n \le 1000$ is guaranteed.

For $50\%$ of the data, $n \le 5000$ is guaranteed.

For all data, $n \le 10000$ is guaranteed.