Minimum Cost to Combine Logs

You are given n logs with specified lengths. Your task is to combine all the logs into one log with minimum cost. Combining any two logs of lengths (x) and (y) incurs a cost of (x+y), and the resulting log has length (x+y). You need to choose the order of combining in such a way that the total cost is minimized.

For example, if you have 4 logs with lengths 4, 3, 2, and 6, one optimal way to combine them would result in a total cost of 29. If there is only one log, no cost is needed.

inputFormat

The first line of input contains an integer (n) representing the number of logs. The second line contains (n) space-separated integers which denote the lengths of the logs.

outputFormat

Output a single integer representing the minimum cost required to combine all the logs into one log.## sample

4
4 3 2 6

29