Merge Alarm

The displayed value of a bundle containing $L$ original pieces is always $L\bmod M$, independently of the merge order.

Let $P$ be the sum of the displayed values of all current bundles. A merge without an alarm leaves $P$ unchanged, while an alarm decreases it by exactly $M$. Initially $P=N$, and finally $P=N\bmod M$. Thus every merge order produces exactly

$$q=\left\lfloor\frac{N}{M}\right\rfloor$$

alarms.

The key sufficiency result is that any set of $q$ boundaries can be the alarm set. For an interval of length $L=qM+r$, its last merge at local boundary $k$ raises an alarm exactly when $k\bmod M>r$. For every target set $S$ of size $\lfloor L/M\rfloor$, there is a split $k$ such that the left side receives exactly $\lfloor k/M\rfloor$ selected boundaries and the membership of $k$ agrees with that alarm condition. Splitting there and applying induction to both children realizes all of $S$.

Therefore the feasible alarm sets are exactly all boundary subsets of size $q$. Choose the $q$ smallest costs. Sorting dominates the running time, so the complexity is $O(N\log N)$.

Solution written by GPT5