> [**Hall 定理：**](https://oi-wiki.org/graph/graph-matching/graph-match/#hall-%E5%AE%9A%E7%90%86)对于一个左部点个数不多于右部点个数的二分图 $G$，设 $N(S)$ 代表 $G$ 中与左部点集合 $S$ 中至少一个点有连边的右部点的集合，则 $G$ 存在完美匹配的充分必要条件是，对于任意的非空左部点集合 $S$，总有 $|N(S)| \ge |S|$。

考虑对于一个给定的权值 $t$ 求解最小权值能够不小于它的最小 $k$ 值。

则对于任意的非空左部点集合 $S$，无论哪 $m - k$ 个右部点被删去，最终的二分图都要有 $|N(S)| \ge |S|$，因此原图中 $|N(S)| \ge |S| + m - k$，即 $k \ge |S| - |N(S)| + m$。

根据 Hall 定理，对所有 $2^n - 1$ 个集合 $S$ 分别计算 $|S| - |N(S)| + m$，取其中的最大值即可得到确保能够完成归还工作的最小 $k$ 值。

考虑倒序枚举 $t = nm, nm - 1, \ldots, 1$，每次会有若干个 $|N(S)|$ 的值减少 $1$（$nm$ 轮中一共会有 $(2^n - 1) \cdot m$ 次减少操作）。由于 $|S| - |N(S)| + m$ 的值总是不大于 $n + m$ 且随枚举过程单调递增，结合双指针开桶统计 $|S| + |N(S)| - m$ 的分布情况即可实现 $O(1)$ 单点修改和 $O(1)$ 查询最大值。

最终的时间复杂度为 $O(2^n \cdot m)$，空间复杂度为 $O(nm + 2^n)$。

（std 中对 $d_{i, j}$ 使用了 `std::sort`，导致实际的时间复杂度为 $O(2^n \cdot m + nm \log nm)$。由于题目保证了矩阵 $\{d_{n, m}\}$ 中的所有元素构成一个 $\{1, 2, \ldots, nm\}$ 的排列，这一点可以使用桶排序来规避。）