CF1408D Searchlights

有 $n$ 个强盗，坐标分别为 $(a_1, b_1)$、$(a_2, b_2)$、…、$(a_n, b_n)$，以及 $m$ 个探照灯，坐标分别为 $(c_1, d_1)$、$(c_2, d_2)$、…、$(c_m, d_m)$。 每次操作，你可以选择将所有强盗向右移动一格（即所有强盗的 $a_i$ 增加 $1$），或者将所有强盗向上移动一格（即所有强盗的 $b_i$ 增加 $1$）。注意，每次操作只能选择一种方式，要么全部增加 $a_i$，要么全部增加 $b_i$，不能对部分强盗增加 $a_i$，对另一部分增加 $b_i$。 如果对于某个探照灯 $j$ 和某个强盗 $i$，有 $a_i \leq c_j$ 且 $b_i \leq d_j$，则探照灯 $j$ 能看到强盗 $i$。 当没有任何探照灯能看到任何强盗时，称当前强盗的分布是安全的（即不存在某对 $i, j$，使得探照灯 $j$ 能看到强盗 $i$）。 请问，最少需要多少次操作才能使强盗达到安全的分布？

输入的第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 2000$），分别表示强盗和探照灯的数量。 接下来的 $n$ 行，每行包含两个整数 $a_i, b_i$（$0 \leq a_i, b_i \leq 10^6$），表示每个强盗的坐标。 接下来的 $m$ 行，每行包含两个整数 $c_i, d_i$（$0 \leq c_i, d_i \leq 10^6$），表示每个探照灯的坐标。

输出一个整数，表示使强盗达到安全分布所需的最少操作次数。

在第一个测试样例中，你可以将所有强盗向右移动三次。此时唯一的强盗坐标为 $(3, 0)$。 此时分布是安全的，因为唯一的探照灯在 $(2, 3)$，且 $3 > 2$，探照灯无法看到强盗。 在第二个测试样例中，你可以将所有强盗向右移动两次，再向上移动两次。此时强盗的坐标为 $(3, 8)$ 和 $(8, 3)$。 很容易看出此时分布是安全的。 可以证明，无法在不超过 $3$ 次操作内达到安全分布。 由 ChatGPT 4.1 翻译