#859. 希蒙的取情报

希蒙的取情报

题目描述

侦察兵希蒙将要前往敌占区域获取我军间谍们冒死得到的情报,敌占区用一个nnmm列的矩阵表示,为了保证情报一定能够传递出来,间谍们将情报复制了kk份分散存放在敌占区。我们知道希蒙通过秘密通道潜入到了敌占区的xxyy列的位置,他要避开其中的pp个敌军的监视区域在最短时间内拿到情报,并且将情报送回,请问我军最短能够在希蒙出发后的几小时后拿到敌军情报。

希蒙只能够从当前区域往上下左右相邻的区域移动,从一个区域移动到另外一个区域的平均时间为1小时,我们假设希蒙总是在匀速运动的,取到情报后也是立马返回。

这个矩形敌占区四周围满了哨塔,所以不能绕出边界然后再回到地图中拿到情报。

输入格式

输入6个正整数 n m p k x y

接下来p行每行输入2个正整数 表示敌军监视区域的行数和列数

再接下来k行每行输入2个正整数 表示情报的存放行数和列数

输出格式

输出一个整数表示我军最短能够在希蒙出发后的几小时后拿到敌军情报。

如果希蒙拿不到情报请输出从起点出发最多能够到达的区域数(包括起点)

样例

输入样例

8 4 7 2 2 4
2 1
2 2
3 3
4 2
6 1
6 2
8 2
3 2
7 2

输出样例

14

样例解释,红色为敌军监视区域,绿色为情报存放点,黄色为起点。

image

输入样例2

8 4 9 2 2 4
2 1
2 2
3 3
4 2
6 1
6 2
8 2
5 2
7 3
3 2
7 2

输出样例2

16

样例解释,因为拿不到情报,包含起点在内最多只能访问16个区域,所以输出16

image

数据范围与提示

5≤n,m≤100

2≤k,p≤10000 出现的坐标均在地图范围内,且所有点不会出现在重复位置。