#L1001. 城楼(Tower)

城楼(Tower)

城楼(Tower)

题目背景

ππ引领数学学院的同学们建造了一座城墙抵抗外星人,他们需要你的帮助共同抵抗外星人。

题目描述

为了抵抗外星人,小ππ建造了 nn 座城楼,每座城楼处于 (xi,yi)( x_i , y_i ) ,城墙是一条线段,从 c1c_1c2c_2 延伸到 c3c_3c4c_4 。同时,有 mm 只外星人位于 (ai,bi)( a_i , b_i ) 。每只外星人会在每分钟内向任意方向移动 11 格。小ππ想要知道,在 dd 分钟内,最坏情况下会有几座城楼被外星人占领?

注意:外星人无法跨过城墙,但可以攻击城墙上的城楼。

输入格式

第一行三个整数 ddnnmm

第二行四个整数 c1c_1c2c_2c3c_3c4c_4

接下来 nn 行,每行两个整数 xi,yix_i , y_i

接下来 mm 行,每行两个整数 ai,bia_i , b_i

输出格式

最坏情况下几座城楼会被占领。

样例 #1

样例输入 #1

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

样例输出 #1

2

提示

所有整数\le 10610^6

例一详解