A shop has n metal bars with given positive integer lengths. A welding machine performs exactly k welds. Each weld takes the two shortest current bars, fuses them into a single bar whose length is their sum, and charges a cost equal to that sum. (If several bars tie for shortest, any of the tied bars may be taken; because ties have equal length, the resulting cost is the same regardless of choice.)
Report the total welding cost across all k welds.
Line 1: two integers n and k.
Line 2: n space-separated positive integers, the bar lengths.
A single integer: the total welding cost after performing exactly k welds.
Example 1
Input
4 2 1 2 3 4
Expected
9
Explanation
Weld 1: take 1 and 2 -> 3 (cost 3), bars become {3,3,4}. Weld 2: take 3 and 3 -> 6 (cost 6). Total = 3 + 6 = 9.
Example 2
Input
3 1 5 2 8
Expected
7
Explanation
The single weld takes the two shortest bars 2 and 5, fusing them for a cost of 7. Total = 7.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →