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

内存限制:128 MiB 时间限制:10 Sec

题目描述

    在得知了自己农场的完整地图后(地图形式如前三题所述),约翰又有了新的问题.他提供
一个整数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

数据范围与提示