[Usaco2004 Feb]Cow Marathon 奶牛马拉松

时间限制:10s      空间限制:128MB

题目描述

    最近美国过度肥胖非常普遍,农夫约翰为了让他的奶牛多做运动,举办了奶牛马拉松.马拉
松路线要尽量长,所以,告诉你农场的地图(该地图的描述与上题一致),请帮助约翰寻找两个
最远农场间的距离.


输入格式

    第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

提示

没有写明提示


题目来源

Green