Add All#1228

Add All

2 seconds

128 megabytes

Very easy

The cost of adding two numbers is equal to their sum. For example, to add $10$ to $1$ , you need to pay $11$ . The task is to add all the given numbers in such a way as to minimize the total cost.

For example, adding the numbers $1$ , $2$ , and $3$ can be done in three ways:

$1 + 2 = 3$ 1 + 2 = 3 (cost $= 3$ ), $3 + 3 = 6$ 3 + 3 = 6 (cost $= 6$ ). Total $= 9$
$1 + 3 = 4$ 1 + 3 = 4 (cost $= 4$ ), $2 + 4 = 6$ 2 + 4 = 6 (cost $= 6$ ). Total $= 10$
$2 + 3 = 5$ 2 + 3 = 5 (cost $= 5$ ), $1 + 5 = 6$ 1 + 5 = 6 (cost $= 6$ ). Total $= 11$

The first method is the cheapest.

Input

The first line contains a positive integer $n (2 \leq n \leq 1 0^{5})$ n~(2 \le n \le 10^5). The second line contains $n$ non-negative integers, each not exceeding $1 0^{5}$ 10^5.

Output

Print the minimum cost of adding all the numbers.

Examples

Example 1

Loading

1 + 2 = 3

3 + 3 = 6

1 + 3 = 4

2 + 4 = 6

2 + 3 = 5

1 + 5 = 6

n (2 \leq n \leq 1 0^{5})

1 0^{5}