题目描述

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

输入格式

第$\red{1}$行：两个分开的整数$\red{N}$和$\red{M.}$

第$\red{2}$到$\red{M+1}$行：每行包括$\red{4}$个分开的内容，$\red{Fi，}$$\red{F2，}$$\red{L，}$$\red{D}$分别描述两个农场的编号，道路的长度，$\red{F1}$到$\red{F2}$的方向$\red{N，}$$\red{E，}$$\red{S，}$$\red{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

提示

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