题目描述

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

输入格式

第 $1$ 行包含两个整数 $N, M$。

第 $2$ 到 $M+1$ 行每行包括 $4$ 个整数 $F_1, F_2, L, D$ 分别描述两个农场的编号，道路的长度，$F_1$ 到 $F_2$ 的方向 $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