Услышав об эпидемии ожирения в США, Farmer John хочет больше упражнений для коров и решил устроить марафон. Маршрут включает две фермы и путь из последовательности дорог между ними. Ради максимальной нагрузки он ищет самые удалённые фермы на карте, измеряя расстояние суммой длин дорог на пути. Помогите найти расстояние между этой самой далёкой парой.

Входные данные

• Строки начиная с 1: тот же формат, что в «Navigation Nightmare».

Выходные данные

• Строка 1: целое расстояние между самой далёкой парой ферм.

Примеры

Входные данные 1

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

Выходные данные 1

52

Примечание

Входные данные

Та же схема ферм, что в задаче 1.

Пояснение — Выходные данные

Самый длинный марафон идёт от фермы 2 по дорогам 4,1,6,3 к ферме 5, длина $20+3+13+9+7=52$.

Автор: Brian Dean, 2004