题目描述

在得知了自己农场的完整地图后（地图形式如前三题所述），约翰又有了新的问题．他提供一个整数 $K$（$1≤K≤10^9$），希望你输出有多少对农场之间的距离是不超过 $K$ 的。

输入格式

第 $1$ 到 $M+1$ 行：与前三题相同。

第 $M+2$ 行：一个整数 $K$。

输出格式

农场之间的距离不超过 $K$ 的对数。

7 6
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S
10

5

提示

有五对道路之间的距离小于 $10$：

• $1-4$，距离为 $3$；
• $4-7$，距离为 $2$；
• $1-7$，距离为 $5$；
• $3-5$，距离为 $7$；
• $3-6$，距离为 $9$。

题目来源

Orange