← 返回题目列表

Codeforces · 1408/D

D. 探照灯

中文机器翻译题面 查看原题

坐标 $$$(a_1, b_1)$$$, $$$(a_2, b_2)$$$, ..., $$$(a_n, b_n)$$$ 处有 $$$n$$$ 劫匪,坐标 $$$(c_1, d_1)$$$, $$$(c_2, $$$(a_n, b_n)$$$ 处有探照灯d_2)$$$,...,$$$(c_m,d_m)$$$。

在一步中,您可以将每个强盗向右移动(每个强盗的 $$$a_i$$$ 增加 1)或向上移动每个强盗(每个强盗的 $$$b_i$$$ 增加 1)。请注意,您应该增加所有 $$$a_i$$$ 或所有 $$$b_i$$$,您不能为某些点增加 $$$a_i$$$,而为其他一些点增加 $$$b_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$$$),探照灯的坐标。

输出

打印一个整数:达到安全配置所需执行的最少移动次数。

示例

输入 #1

1 1
0 0
2 3

输出 #1

3

输入 #2

2 3
1 6
6 1
10 1
1 10
7 7

输出 #2

4

输入 #3

1 2
0 0
0 0
0 0

输出 #3

1

输入#4

7 3
0 8
3 8
2 7
0 10
5 5
7 0
3 5
6 6
3 11
11 5

输出#4

6

注意

在第一个测试中,您可以将每个强盗向右移动 3 次。之后,坐标 $$$(3, 0)$$$ 中将会出现一名强盗。

强盗的配置是安全的,因为唯一的探照灯看不到强盗,因为它位于坐标 $$$(2, 3)$$$ 且 $$$3 > 2$$$ 中。

在第二个测试中,你可以将每个强盗向右移动两次,向上移动两次。之后强盗将位于坐标$$$(3, 8)$$$、$$$(8, 3)$$$。

很容易看出盗贼的配置是安全的。

可以证明,使用不超过 $$$3$$$ 的移动就无法达到安全配置。