1120. Only m Joins Allowed

n piles of sand sit in a yard. One JOIN takes any two piles and merges them at a cost equal to their combined size. You are allowed exactly m joins, no more and no fewer, and m is never more than n - 1.

Print the smallest total cost of m joins.

piles 8 4 6 12 2, m = 2 -> 18 piles 8 4 6 12 2, m = 4 -> 70 piles 1 2 3 4, m = 0 -> 0 piles 5 5 5, m = 1 -> 10

Trace the first line. Join 2 and 4 for 6, leaving 8 6 6 12. Join the two 6s for 12, leaving 8 12 12. The total is 6 + 12 = 18. Any other pair of joins costs more: joining 2 and 4 then 6 and 6 is what was just done, and joining 2 and 4 then 6 and 8 costs 6 + 14 = 20.

## What most people try first

Joining the two SMALLEST ORIGINAL piles m times, without putting the result back. On 8 4 6 12 2 with m = 2 that joins 2 and 4 for 6, then 6 and 8 for 14, giving 20 instead of 18. The pile produced by the first join is itself small and must compete for the second join.

The other instinct is that stopping early changes the rule. It does not: the rule is the same as for a full merge, the loop simply runs fewer times. What changes is that the answer is no longer "the total weighted by depth", because most piles never get buried at all.

Trying every sequence of m joins costs about (n choose 2)^m.

## The method

put every size into a min-heap total = 0 repeat m times: x = pop, y = pop total = total + x + y push x + y

m iterations of two pops and one push, so O((n + m) log n).

## Why the two smallest, even when stopping early

Induct on m. For m = 0 there is nothing to prove.

For the step, let a and b be the two smallest piles. Claim: some optimal sequence of m joins begins by joining a and b.

Take an optimal sequence and look at its FIRST join, which merges piles p and q.

If neither a nor b is involved, replace that join by joining a and b instead. The cost of the first join falls, since a + b <= p + q. Every later join in the sequence referred to p + q or to untouched piles; rewrite it to refer to a + b in the same position of the merge tree. Each later join's cost either stays the same or falls by (p + q) - (a + b), which is not negative. So the new sequence costs no more.

If exactly one of them is involved, say p = a and q is neither a nor b, replace q by b. The first join costs a + b <= a + q, and the same rewriting applies downstream.

Either way an optimal sequence starting with a and b exists. Remove that join, and what remains is an optimal sequence of m - 1 joins on the new multiset, which is the induction hypothesis.

## The boundary that breaks a careless implementation

m = 0 answers 0 and the heap is never touched. A loop written as "while more than one pile remains" ignores m entirely and answers the full merge cost.

m = n - 1 is the full merge and must give the same number as joining everything, which is problem #596's answer for the same multiset. The fifth and ninth tests check both ends.

Piles of size 0 are legal and cost nothing to join.

## Sizes

n reaches 1000 and a size reaches 10^9, so the total of all piles reaches 10^12 and the answer reaches about 10^15 when m is large. That is far past the 2147483647 limit of a signed 32-bit integer, and five piles of 10^9 with two joins already cost 5 * 10^9, which the eighth test checks.

## Related problems

Problem #596 is this problem with m fixed at n - 1, and problem #1119 is the same operation maximised instead of minimised. Problem #1121 changes how many piles one join may take.

Constraints - `1 ≤ n ≤ 1000` - `0 ≤ m ≤ n - 1` - `0 ≤ size ≤ 1000000000`