时间限制： 1.0 秒

空间限制： 256 MB

题目描述

目前在一个很大的平面房间里有 $n$ 个无线路由器，每个无线路由器都固定在某个点上。任何两个无线路由器只要距离不超过 $r$ 就能互相建立网络连接。

除此以外，另有 $m$ 个可以摆放无线路由器的位置。你可以在这些位置中选择至多 $k$ 个增设新的路由器。

你的目标是使得第 $1$ 个路由器和第 $2$ 个路由器之间的网络连接经过尽量少的中转路由器。请问在最优方案下中转路由器的最少个数是多少？

输入格式

从标准输入读入数据。

第一行包含四个正整数 $n,m,k,r$ 。

接下来 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$，表示一个已经放置好的无线路由器在 $(x_i, y_i)$ 点处。输入数据保证第 $1$ 和第 $2$ 个路由器在仅有这 $n$ 个路由器的情况下已经可以互相连接（经过一系列的中转路由器）。

接下来 $m$ 行，每行包含两个整数 $x_i$ 和 $y_i$，表示 $(x_i, y_i)$ 点处可以增设 一个路由器。

输出格式

输出到标准输出。

输出只有一个数，即在指定的位置中增设 $k$ 个路由器后，从第 $1$ 个路由器到第 $2$ 个路由器最少经过的中转路由器的个数。

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

2

数据范围

对于所有数据，保证 $2 \le n \le 100,~1 \le k \le m \le 100,~1 \le r \le 10^8$，输入中所有的坐标的绝对值不超过 $10^8$，保证输入中的坐标各不相同。