Problems
Add All
Add All
The cost of adding two numbers equals to their sum. For example to add 1 and 10 costs 11. The cost of addition 1 and 2 is 3. We can add numbers in several ways:
1 + 2 = 3 (cost = 3), 3 + 3 = 6 (cost = 6). Total = 9
1 + 3 = 4 (cost = 4), 2 + 4 = 6 (cost = 6). Total = 10
2 + 3 = 5 (cost = 5), 1 + 5 = 6 (cost = 6). Total = 11
We hope you understood the task. You must add all numbers so that the total cost of summation will be the smallest.
Input data
First line contains positive integer n~(2 \le n \le 10^5). Second line contains n nonnegative integers, each no more than 10^5.
Output data
Print the minimum total cost of summation.
Examples
Input example #1
3 1 2 3
Output example #1
9