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$ 。（也就是说，一次操作中，要么使所有强盗的 $a_i$ 加 $1$ ,要么使所有强盗的 $b_i$ 加 $1$ ，修改操作是针对所有的强盗统一进行的。） 探照灯 $j$ 可以看到强盗 $i$ 当且仅当 $a_i≤c_j$ 且 $b_i≤d_j$。 如果没有探照灯能看见强盗，则成为这种强盗的布局是安全的。（即，不存在一对 $i,j$ 使得探照灯 $j$ 可以看到强盗 $i$ ）。 那么如果想达到一个安全的布局，你需要执行的最小移动次数是多少呢？

题目描述

There are $ n $ robbers at coordinates $ (a_1, b_1) $ , $ (a_2, b_2) $ , ..., $ (a_n, b_n) $ and $ m $ searchlight at coordinates $ (c_1, d_1) $ , $ (c_2, d_2) $ , ..., $ (c_m, d_m) $ . In one move you can move each robber to the right (increase $ a_i $ of each robber by one) or move each robber up (increase $ b_i $ of each robber by one). Note that you should either increase all $ a_i $ or all $ b_i $ , you can't increase $ a_i $ for some points and $ b_i $ for some other points. Searchlight $ j $ can see a robber $ i $ if $ a_i \leq c_j $ and $ b_i \leq d_j $ . A configuration of robbers is safe if no searchlight can see a robber (i.e. if there is no pair $ i,j $ such that searchlight $ j $ can see a robber $ i $ ). What is the minimum number of moves you need to perform to reach a safe configuration?

输入输出格式

输入格式

The first line of input contains two integers $ n $ and $ m $ ( $ 1 \leq n, m \leq 2000 $ ): the number of robbers and the number of searchlight. Each of the next $ n $ lines contains two integers $ a_i $ , $ b_i $ ( $ 0 \leq a_i, b_i \leq 10^6 $ ), coordinates of robbers. Each of the next $ m $ lines contains two integers $ c_i $ , $ d_i $ ( $ 0 \leq c_i, d_i \leq 10^6 $ ), coordinates of searchlights.

输出格式

Print one integer: the minimum number of moves you need to perform to reach a safe configuration.

输入输出样例

输入样例 #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

说明

In the first test, you can move each robber to the right three times. After that there will be one robber in the coordinates $ (3, 0) $ . The configuration of the robbers is safe, because the only searchlight can't see the robber, because it is in the coordinates $ (2, 3) $ and $ 3 > 2 $ . In the second test, you can move each robber to the right two times and two times up. After that robbers will be in the coordinates $ (3, 8) $ , $ (8, 3) $ . It's easy the see that the configuration of the robbers is safe. It can be proved that you can't reach a safe configuration using no more than $ 3 $ moves.