Reduce the Array (Also for DA)

Each time, choose elements at two different positions, remove them, and insert their sum; the cost of this step is that sum. Find the minimum total cost to merge everything into a single element.

输入格式

The first line contains n, followed by n positive integers; full original bounds 2≤n≤100000, 1≤a[i]≤100.

输出格式

Output a single integer answer.

样例 1

输入：

3
25 10 20

输出：

85

样例 2

输入：

2
1 1

输出：

2

样例 3

输入：

4
2 3 4 5

输出：

28

样例说明

The outputs of the three public examples are, in order: 85; 2; 28. These answers have been checked by independent enumeration or direct simulation.