Minimum Cost to Connect Ropes

Zara has n ropes of various lengths. She wants to connect all the ropes into one continuous rope. The process of connecting two ropes costs the sum of their lengths. To minimize the total cost, Zara follows a greedy strategy: she always connects the two shortest ropes available.

Mathematically, if you connect two ropes with lengths \(a\) and \(b\), the cost is \(a+b\). After each connection, the newly formed rope of length \(a+b\) is used in further connections. The task is to determine the minimum total cost required to connect all the ropes into one rope, which can be expressed as:

$$\text{Total Cost} = \sum_{i} (a_i+b_i)$$

inputFormat

The first line contains an integer \(n\) representing the number of ropes.

The second line contains \(n\) space-separated positive integers representing the lengths of the ropes.

outputFormat

Output a single integer representing the minimum total cost to connect all the ropes into one continuous rope.

4
4 3 2 6

29