eolymp
bolt
Try our new interface for solving problems
Problems

Add All

Add All

Time limit 2 seconds
Memory limit 128 MiB

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