#P2226. 疫情控制

疫情控制

据某省水产部门通报,A市大面积范围水产养殖区爆发ADH氏菌疫情,导致大量鱼苗死亡,养殖户经济损失巨大。必须尽快控制疫情,使水产养殖秩序回归正常。<o:p></o:p>

此次ADH氏菌疫情传染范围较大,涉及到 M 地区。要想对某个地区I疫情进行控制,必须先控制住上游地区I-1的疫情,再对该地区监测,管理,施药才能彻底清除传染性,真正做到水体改良,水质改善。<o:p></o:p>

 

不妨设M 地区的编号12M,首先,地区1的疫情得到控制后,才能在1天后控制地区2。类推,仅当地区i的疫情得到控制后,1天后才能去控制地区i+1;当第M个地区疫情被控制后,才算彻底控制住A市疫情。<o:p></o:p>

 

如何做到早发现,早报告,早隔离,早治理,按照属地化管理原则,A市准备建立 N 个防疫中心。当一个防疫中心启用后,它可以对方圆半径 R 范围内的地区疫情加以控制,并且持续控制5天。N 个防疫中心也不是同时启动,当一个防疫中心启用5天后,才能启动另一个防疫中心。<o:p></o:p>

 

启用一个防疫中心需要大量的人力,物力。请你设计一个方案,如何启用尽可能少的防疫中心就能够对A市所有疫情加以控制。<o:p></o:p>

Input

第一行: K 表示有多少组测试数据。
接下来对每组测试数据:
第1行: M N R
第2~M+1行: X1i Y1 i 表示第 i 地区所在的坐标 i=1,…,M
第M+2~M+N+1行: X2 j Y2j 表示第 j 防疫中心的坐标 j=1,…,N
1≤K≤5 1 ≤M, N ≤ 100,1≤ R≤1000, 0≤所有坐标X,Y≤10000
所有数据都是整数。 数据之间有一个空格。

Output

对于每组测试数据,输出占一行:最少启用的防疫中心数量

Sample Input

1
4 3 6
0 6
6 6
6 0
0 0
0 3
1 1
1 5

Sample Output

</p>
2 

HINT

启用3号防疫中心可以控制地区1,2
启用2号防疫中心可以控制地区3,4

Source