The Scrap Baler's Bill

A scrapyard has piles of metal with weights weights. Its baler presses between 2 and k piles (inclusive) together into one new pile whose weight is the sum of theirs, and each press is billed the weight of the new pile. The yard keeps pressing until exactly one pile is left.

Return the smallest possible total bill. A yard with zero or one pile pays 0.

Examples

Input:  weights = [1, 1, 1, 1], k = 3
Output: 6
Explanation: press two piles (bill 2), then press the three piles 2, 1, 1 (bill 4).
             Pressing three piles first costs 3 + 4 = 7.

Input:  weights = [4, 3, 6, 2, 5], k = 3
Output: 29
Explanation: press 2, 3, 4 (bill 9), then 5, 6, 9 (bill 20).

Constraints

• 0 <= len(weights) <= 2 * 10**5
• 0 <= weights[i] <= 10**6
• 2 <= k <= 10**5 (k may exceed the number of piles)
• Re-sorting the piles after every press is too slow for the largest tests.

Goals

• Generalise pairwise cheapest-first merging to presses that take up to k piles
• See why the one short press must happen first, and how big it must be
• Drive the merging with a min-heap in O(n log n)