Description

在得知了自己农场的完整地图后（地图形式如前三题所述），约翰又有了新的问题．他提供

一个整数K(1≤K≤109)，希望你输出有多少对农场之间的距离是不超过K的．

Format

Input

第1到I+M行：与前三题相同；

第M+2行：一个整数K.

Output

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

Samples

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

Limitation

有五对道路之间的距离小于10 1-4,距离为3 4-7,距离为2 1-7,距离为5 3-5,距离为7 3-6,距离为9