Connect the cables
Given
n cables with their lengths, you would like to connect all those cables together and obtain one big cable. To connect two cables with lengths x and y, you should pay x + y. After connecting those, the resulting cable has a length of x + y. What is the minimum amount you would spend on connecting all the cables?
Input
The first line of the input contains a single integer
n (1 ≤ n ≤ ) the number of cables.The next line contains space-separated integers
Output
The program should print the minimum amount you would spend on connecting those cables.
Examples
Input | Output |
5
1 2 3 6 2 | 30 |
Explanation
- Connect 1 and 2 ⇒ pay 3 ⇒ 3 3 6 2
- Connect 2 and 3 ⇒ pay 5 ⇒ 5 3 6
- Connect 3 and 5 ⇒ pay 8 ⇒ 6 8
- Connect 6 and 8 ⇒ pay 14
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB