解题思路

核心观察 颜色平衡条件：设每种颜色买 $t$ 个，则总数为 $k \times t$ 模运算性质：重量在模 $m$ 意义下具有可加性 分组处理：相同颜色的糖豆放在一组考虑

算法设计

第一步：预处理每个颜色对于每个颜色 $i$，我们计算数组 $f_i[r]$：表示用该颜色的糖豆组合出总重量模 $m$ 为 $r$ 的最小花费。这可以用模意义下的最短路算法解决：

把 $0$ 到 $m-1$ 看作图中的节点对于该颜色的每个糖豆 $(w, c)$，从每个节点 $u$ 向 $(u+w) \bmod m$ 连边，边权为 $c$用 Dijkstra 算法求从 $0$ 出发到各点的最短路

第二步：合并所有颜色

设 $dp[i][r]$ 表示前 $i$ 种颜色总重量模 $m$ 为 $r$ 的最小花费。初始：$dp[0][0] = 0$，其余为无穷大转移：对于第 $i$ 种颜色，枚举当前余数 $j$ 和该颜色能提供的余数 $r$：dp[i][(j+r) mod m]=min(dp[i][(j+r) mod m],dp[i−1][j]+fi[r]) dp[i][(j+r)modm]=min(dp[i][(j+r)modm],dp[i−1][j]+fi[r])

最终 $dp[k][r]$ 就是答案。