题目描述

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

输入格式

第$\red{1}$到$\red{I+M}$行：与前三题相同；

第$\red{M+2}$行：一个整数$\red{K.}$

输出格式

农场之间的距离不超过$\red{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

提示

有五对道路之间的距离小于$\red{10}$

$\red{1-4,}$距离为$\red{3}$

$\red{4-7,}$距离为$\red{2}$

$\red{1-7,}$距离为$\red{5}$

$\red{3-5,}$距离为$\red{7}$

$\red{3-6,}$距离为$\red{9}$