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.
Input format
Line 1: two integers n and k.
Line 2: n space-separated positive integers, the bar lengths.
Output format
A single integer: the total welding cost after performing exactly k welds.
Constraints
- 2 <= n <= 100000
- 1 <= k <= n - 1
- 1 <= each length <= 1000000