#3365. [Usaco2004 Feb]Distance Statistics 路程统计

题目描述

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

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

输入格式

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

第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

数据范围与提示