Array Reduction 1

Each time, choose two elements at different positions, pay their sum, and replace the two elements with that sum. Continue until only one element remains, and find the minimum total cost.

输入格式

The first line contains n, and the second line contains n integers. Full original bounds: 2≤n≤10000, 0≤a[i]≤100000. The answer may exceed the range of a 32-bit integer.

输出格式

Output a single integer, the answer.

样例 1

输入：

3
4 6 8

输出：

28

样例 2

输入：

3
1 2 3

输出：

9

样例 3

输入：

3
0 0 9

输出：

9

样例说明

The outputs of the three public examples are, in order: 28; 9; 9. They were verified by independent enumeration or direct simulation.