Minimum Cost to Tie Ropes

You are given n ropes, each with a positive integer length. Your task is to connect all the ropes into one rope with the minimum cost. The cost to connect two ropes is equal to the sum of their lengths. You can connect the ropes in any order.

Formally, if you connect two ropes with lengths a and b, the cost incurred is a+b. After connecting them, the two ropes become a single rope of length a+b. You repeat this process until there is only one rope left.

The problem can be solved using a greedy approach with a min-heap. At each step, pick the two smallest ropes, connect them, and add the cost. The overall minimum cost is the sum of all individual connection costs.

In mathematical form, if the sequence of operations produces intermediate sums \(S_1, S_2, \ldots, S_{n-1}\), then the final answer is:

[ \text{Total Cost} = \sum_{i=1}^{n-1} S_i ]

inputFormat

The input is given from standard input (stdin). The first line contains an integer n representing the number of ropes. The second line contains n space-separated integers representing the lengths of the ropes.

outputFormat

Output to standard output (stdout) a single integer: the minimum cost to tie all the ropes into one rope.## sample

4
4 3 2 6

29