题解

思路

箱先生只需在现有箱子无法容纳当前颜色时买新箱。

做法

把买箱后的剩余容量记为 $V_i-1$：未凑齐 $M$ 个活跃颜色前，买箱净花费 $P_i-1$；凑齐后，球先生会优先填满剩余容量最小的颜色，于是每买够并淘汰一个箱，就额外得到对应的 $V_i-1$。若最终买了若干箱，最大的 $M-1$ 个剩余容量不会产生这部分收益，其余箱子的贡献为 $V_i-P_i$。

按 $V_i$ 降序，枚举被选择箱中按此顺序第 $M$ 个箱。它之前应选价格最小的 $M-1$ 个箱并支付 $P_i-1$，它之后所有 $V_i-P_i>0$ 的箱都应选择。

复杂度

用大根堆维护前缀最小的 $M-1$ 个价格，并预处理后缀正贡献即可在 $O(N\log N)$ 时间、$O(N)$ 空间内求出每组答案。