Merging Fruits

Problem Description

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

In each merge, Duoduo may combine two piles into one; the physical effort consumed equals the sum of the weights of the two piles. After $n - 1$ merges, only one pile remains. The total effort Duoduo spends equals the sum of the efforts of every individual merge.

Because the fruits still have to be carried home afterwards, Duoduo wants to save as much effort as possible when merging. Suppose each fruit weighs exactly $1$, and the number of types and the count of each type are known. Your task is to design an order of merges that minimizes Duoduo's total effort, and output that minimum value.

For example, suppose there are $3$ types of fruit with counts $1, 2, 9$. Duoduo can first merge the piles of size $1$ and $2$ into a new pile of size $3$, spending $3$ units of effort. Then merge that new pile with the original third pile, obtaining a pile of size $12$, spending $12$ units of effort. The total effort is $3 + 12 = 15$. It can be proven that $15$ is the minimum possible total effort.

Input Format

The input consists of two lines. The first line contains an integer $n$ ($1 \le n \le 30000$), 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 count of the $i$-th type of fruit.

Output Format

Output a single line containing only the minimum total effort. The input guarantees this value is less than $2^{31}$.

Sample Input 1

3
1 2 9

Sample Output 1

15

Sample Input 2

10
3 5 1 7 6 4 2 5 4 1

Sample Output 2

120

Constraints

Time limit: 1s; memory limit: 1024 KiB for each test case.