Question
The Blacksmith's Chain Forging
A blacksmith has
Welding two rods together costs an amount equal to the sum of their current lengths, and the resulting welded piece can then be welded again to others. Find the minimum total cost to weld all the rods into one single piece.
Input
The first line contains a single integer KaTeX can only parse string typed expression — the number of rods.
The second line contains KaTeX can only parse string typed expression integers — the lengths of the rods.
Output
Print a single integer — the minimum total welding cost to combine all rods into one.
Example
Example 1:
Input
Weld the 2 and 3 length rods first, cost 5, leaving pieces {5,4,6}. Weld the 4 and 5 pieces, cost 9, leaving {9,6}. Weld 9 and 6, cost 15. Total = 5+9+15 = 29, the minimum possible.
Example 2:
Input
A single rod needs no welding, so the cost is 0.
Input
4
4 3 2 629Weld the 2 and 3 length rods first, cost 5, leaving pieces {5,4,6}. Weld the 4 and 5 pieces, cost 9, leaving {9,6}. Weld 9 and 6, cost 15. Total = 5+9+15 = 29, the minimum possible.
Example 2:
Input
1
50A single rod needs no welding, so the cost is 0.