Given n ropes of different lengths, you need to connect these ropes into one rope. You can connect only 2 ropes at a time. The cost required to connect 2 ropes is equal to the sum of their lengths. The length of this connected rope is also equal to the sum of their lengths. This process is repeated until n ropes are connected into a single rope.
Find the minimum possible cost required to connect all ropes.
Input
The input consists of an argument:
ropes: an int array representing the rope length
Output
Return the minimum possible cost required to connect all ropes.
Examples
Example 1
Input[8, 4, 6, 12]
Output58
Explanation
The optimal way to connect ropes is as follows
Connect the ropes of length 4 and 6 (cost is 10). Ropes after connecting: [8, 10, 12]
Connect the ropes of length 8 and 10 (cost is 18). Ropes after connecting: [18, 12]
Connect the ropes of length 18 and 12 (cost is 30).
Total cost to connect the ropes is 10 + 18 + 30 = 58
Example 2
Input[20, 4, 8, 2]
Output54
Example 3:
Input[1, 2, 5, 10, 35, 89]
Output224
Example 4:
Input[2, 2, 3, 3]
Output20