传送门：https://atcoder.jp/contests/abc332/tasks/abc332_g
看完题，第一眼反应为最大流。
建模方式为：以颜色为左部点，盒子为右部点，源点 $S$ 向颜色 $i$ 连一条容量为 $A_i$ 的边，盒子 $j$ 向汇点 $T$ 连一条容量为 $B_j$ 的边，颜色 $i$ 向盒子 $j$ 连一条容量为 $ij$ 的边；在这张图上跑最大流即可得到答案。
但问题来了：这张图一共有 $O(n+m)$ 个点，$O(nm)$ 条边，$Dinic$ 最大流的复杂度为 $O(V^2E)$，在本题显然难以接受。
考虑能否优化最大流。一个比较常规的想法是，由于最大流=最小割，所以我们可以尝试从最小割的角度思考，或许不需要使用最大流算法即可求出最小割。
（注：以下 $i$ 均代表颜色，$j$ 均代表盒子）
最小割的要求是“割完边后的图中不能存在 $S$ 到 $T$ 的路径”，而要满足这个要求，对于任意一组 $i$ 和 $j$，$(S$, $i)$、$(i$, $j)$、$(j$, $T)$ 三条边中，必须至少有一条被割掉（否则就会形成路径）；而如果 $(S$, $i)$、$(j$, $T)$ 之中有至少一条边被割，那么 $(i$, $j)$ 显然就没有割的必要了；
因此，设我们割掉 $S$ 到集合 $S_1$ 中的颜色的边、集合 $S_2$ 中的盒子到 $T$ 的边，代价为 $\sum_{i\in S_1}A_i+\sum_{j\in S_2}B_j+\sum_{i\notin S_1}\sum_{j\notin S_2}ij=\sum_{i\in S_1}A_i+\sum_{j\in S_2}B_j+(\sum_{i\notin S_1}i)(\sum_{j\notin S_2}j)$，而我们要求出这个式子的最小值；
观察到 $N$ 的范围只有 $500$，所以考虑从颜色入手；容易发现我们可以枚举 $\sum_{i\notin S_1}i$（以下记作 $sumi$），而如果确定了 $sumi$ 的值，那么 $\sum_{i\in S_1}A_i$（以下记作 $sumAi$）越小越好，它的最小值我们可以预先 $dp$ 求出（比较简单，此处略过）；此时我们相当于枚举了一组 $sumi、sumAi$ 的值；
而在 $sumi、sumAi$ 确定的情况下，对于每个 $j$，如果它进入 $S_2$，它会对式子带来 $B_j$ 的贡献；反之，它会带来 $sumi*j$ 的贡献；所有 $j$ 的选择（是否进入 $S_2$）是彼此无关的，所以对于每个 $j$，它的贡献直接取二者的最小值即可，即 $min(B_j,sumi*j)$；
下面要做的事就仅剩：在 $sumi、sumAi$ 确定的情况下，快速计算 $\sum_{j=1}^{M}min(B_j,sumi*j)$；考虑消去 $min$，对于每个 $j$ 而言，在 $sumi<=\lfloor{B_j/j}\rfloor$ 时，取 $sumi*j$ 更优，反之取 $B_j$ 更优；我们把所有 $j$ 按照 $\lfloor{B_j/j}\rfloor$ 排序，则对于任意 $sumi$，满足 $sumi<=\lfloor{B_j/j}\rfloor$ 的 $j$ 一定是区间右侧一段，不满足的一定是区间左侧一段；从小到大枚举 $sumi$，每次右移 $j$ 的两段之间的分隔线，提前计算排序后的 $j$ 序列上 $j$ 和 $B_j$ 分别的前缀和，即可在总共 $O(n^2+m)$ 的时间内计算出所有 $sumi$ 对应的最优答案，取 $min$ 即为题目答案。