J9 习题-3 奶牛马拉松

题目描述

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

图中农场用 $F_1\ldots F_7$表示, 每个农场最多能在东西南北四个方向连结 $4$ 个不同的农场．此外，农场只处在道路的两端。

输入格式

第一行：两个分开的整数 $N$ 和 $M$；

第二到 $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$。

数据范围

对于 $100\%$ 的数据：$2 \le N \le 40000$，$2 \le M \le 40000$。