Grakn Forces 2020 D. Searchlights——贪心

D. Searchlights

Description

There are n robbers at coordinates (a1,b1), (a2,b2), …, (an,bn) and m searchlight at coordinates (c1,d1), (c2,d2), …, (cm,dm).

In one move you can move each robber to the right (increase ai of each robber by one) or move each robber up (increase bi of each robber by one). Note that you should either increase all ai or all bi, you can’t increase ai for some points and bi for some other points.

Searchlight j can see a robber i if ai≤cj and bi≤dj.

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?

Input

The first line of input contains two integers n and m (1≤n,m≤2000): the number of robbers and the number of searchlight.

Each of the next n lines contains two integers ai, bi (0≤ai,bi≤106), coordinates of robbers.

Each of the next m lines contains two integers ci, di (0≤ci,di≤106), coordinates of searchlights.

Output

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

Examples

input

1 1
0 0
2 3

output

3

input

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

output

4

input

1 2
0 0
0 0
0 0

output

1

input

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

output

6

Note

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.

题意： n个强盗，第i个强盗所处的位置用坐标（a_i，b_i）表示，又有m盏探照灯，第i盏探照灯所布置的位置用（c_i，d_i）表示。强盗要通过移动来躲避探照灯，他们只能往右移、往上移，往右移一步a_i加一，往上移b_i加一，且移动时所有强盗的坐标一起移动。当a_i、b_i中任意一个的值比探照灯的坐标中的任意一个值大时，此强盗可以逃脱追捕，求最小的移动步数。

题解： 贪心思想：先向上（或者向右）移动，找出向上移动需要移动的最大步数（即d_i与b_i的最大差值），再枚举向右走的步数与向上走的步数的最小和。

c++ AC 代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 2e3 + 10;

int a[maxn], b[maxn], c[maxn], d[maxn];

int cnt[maxn * maxn];

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%d%d", a + i, b + i);
	for (int i = 1; i <= m; i++)
		scanf("%d%d", c + i, d + i);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (a[i] <= c[j])
				cnt[c[j] - a[i]] = max(cnt[c[j] - a[i]], d[j] - b[i] + 1);
	int big = 0, ans = 1e9;
	for (int i = 1000001; i >= 0; i--)
	{
		big = max(big, cnt[i]);
		ans = min(i + big, ans);
	}
	printf("%d\n",ans);
	// system("pause");
	return 0;
}

代码参考自：https://blog.csdn.net/qq_45458915/article/details/108903641