问题可以转化为左右都是 $n$ 个点的二分图，连 $m$ 条边，要求最大匹配在 $l$ 和 $r$ 之间，每个点根据度数有一个代价，最小化每个点代价的和。

假设确定了一个每个点的度数，并求出了最大匹配的最小和最大值，那么在这个区间内的所有数都可以取到：从最小值开始，每次在两边各找一个度数不为 $0$ 的非匹配点 $x$ 和 $y$，假设它们分别向 $u$ 和 $v$ 有边（$u$, $v$ 显然是匹配点），则删去边 $(x,u)$ 和 $(v,y)$，加入边 $(x,y)$ 和 $(v,u)$，能使得最大匹配恰好增加 $1$。

根据 Hall 定理，最大匹配等于 $|X|+\min_{S\subseteq X}\{|N(S)|-|S|\}$。因此，要最大匹配的最小值 $\le r$，只需存在一个子集 $S$ 使得 $|X|+|N(S)|-|S|\le r$。

最大匹配的最大值显然是两边度数非零的点数的较小值。因此，要最大值 $\ge l$，只需要两边都有至少 $l$ 个度数非零的点。

考虑 DP，分别 DP 出两边点集大小为 $i$，点集中的度数和为 $j$ 的最小代价。DP 过程中还需要记录度数非零的点数以及总度数，总复杂度为 $O(n^3m^3)$。

DP 完之后，枚举所有合法的状态对更新答案。最后按上文所述构造方案即可。