题目描述

疯狂科学家面条老师通过时光机器将自己分裂成了许多不同时期的自己。这些不同的面条老师分散在一个二维平面上。

当全部的面条老师聚集到某个整点上时，面条老师将迎来重生，获得巨大的力量。

平面中有一种点位称为虫洞，虫洞可以不消耗时间地相互通行。

对于每个面条老师，他可以：

• 消耗一秒向上下左右的相邻整点移动。
• 当位于虫洞时，可以不消耗时间地移动到任意一个其他虫洞的位置。
• 保持不动。

你的任务是计算将全部的面条老师重新聚集到某个整点的最少时间。

输入格式

第一行两个整数$n, m$，表示一共有$n$个面条老师，共有$m$个点位是虫洞。

接下来$n$行，每行两个整数$x, y$表示一个面条老师的坐标。

接下来$m$行，每行两个整数$x, y$表示一个虫洞的位置。

输出格式

输出一行一个整数，表示所有面条老师聚集到某个点上的最早时间。

2 2
5 -3
-4 -5
-4 0
-3 -2

6

数据规模与约定

对于10%的数据，$m = 1$

对于另外20%的数据，$n, m \le 100, -100 \le x_i, y_i \le 100$

对于另外10%的数据，$m \le 20$

对于另外15%的数据，$n \le 10^4, m \le 100$

对于100%的数据，$n \le 10^5, m \le 10^5, -10^8 \le x_i, y_i \le 10^8$

大样例

大样例下载