#P3365. [Usaco2004 Feb]Distance Statistics 路程统计
[Usaco2004 Feb]Distance Statistics 路程统计
题目描述
有 个农场,编号为 到 。它们由 条双向道路连接,任意两个农场之间恰有一条简单路径。两农场的距离是这条路径上各条道路长度之和。
,。每条道路的长度是 到 的整数。
给定整数 ,求有多少对不同的农场距离不超过 。同一对农场只计一次。
输入格式
第一行两个整数 。
接下来 行,每行两个农场编号 、一个道路长度 和一个字符 。字符 N、E、S、W 表示从 到 的方位。每条道路均可双向通行。
最后一行给出一个整数 ,满足 。
输出格式
输出一个整数,表示满足要求的无序农场对数。
样例
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