#3363. [Usaco2004 Feb]Cow Marathon 奶牛马拉松

题目描述

最近美国过度肥胖非常普遍，农夫约翰为了让他的奶牛多做运动，举办了奶牛马拉松．马拉

松路线要尽量长，所以，告诉你农场的地图（该地图的描述与上题一致），请帮助约翰寻找两个

最远农场间的距离．

输入格式

第1行：两个分开的整数N和M.

第2到M+1行：每行包括4个分开的内容，Fi，F2，L，D分别描述两个农场的编号，道路的长

度，F1到F2的方向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

样例输出

52  

  最长的马拉松路线从2通过4，1，6，3到5；总长为：20+3+12+9+7=52

数据范围与提示