In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of January 4th
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #12 exercise sheet]

[AED073] Rope Connections

Leo has N ropes of different lengths and he wants to tie them all into a single big rope. The cost to connect two ropes is equal to sum of their lengths. Of course Leo wants to connect all the ropes with the minimum cost possible!

For example, suppose we have 4 ropes of lengths 7, 3, 5, and 1:

• One (not optimal) solution would be to combine the 7 and 3 rope for a rope of length 10, then combine this new length 10 rope with the length 5 rope for a rope of length 15, then combine the rope of length 15 with the rope of length 1 for a final rope of length 16. The total cost would be 10 + 15 + 16 = 41.
• If he first combines ropes 1 and 3 he will form a rope of length 4. Then he could combine this one with the rope of length 5 to form a rope of length 9. He could combine this rope with the rope of length 7 to form a final rope of length 16. The total cost would be 4+9+16=29 (which is the minimum cost for this case).

Can you help Leo discover how to connect the ropes for a general cases?

The Problem

Given a list of N lengths of ropes, your task is to compute the minimum cost possible to form a single large rope assuming the cost to connect two ropes is equal to sum of their lengths.

Input

The first line of input contains an integer N, indicating the number of ropes to consider.

The second line contains N integers L₁, L₂, ..., X_N, the lengths of the ropes (note that some lengths might be equal).

Output

The output should be a line containing the minimum possible cost to join all the ropes into a single rope.

Constraints

The following limits are guaranteed in all the test cases that will be given to your program:

4
7 3 5 1

29

Explanation of Example Input 1

This example is explained in the problem statement.

5
18 2 2 2 2

42

Explanation of Example Input 2

One way to obtain cost 42 would be:

• Join a rope of length 2 with a rope of length 2 (with a cost of 4) | now Leo has 4 ropes with the following lengths: 18,2,2,4
• Join a rope of length 2 with a rope of length 2 (with a cost of 4) | now Leo has 3 ropes with the following lengths: 18,4,4
• Join a rope of length 4 with a rope of length 4 (with a cost of 8) | now Leo has 2 ropes with the following lengths: 18,8
• Join a rope of length 18 with a rope of length 8 (with a cost of 26) | now Leo has 1 final rope of length 26

The total cost is 4+4+8+26=42.