Po usłyszeniu o epidemii otyłości w USA Farmer John chce więcej ruchu dla krów i organizuje krowi maraton. Trasa obejmuje dwie farmy i ścieżkę z kolejnych dróg między nimi. Dla jak największego wysiłku szuka dwóch najodleglejszych farm na mapie, mierząc odległość sumą długości dróg na ścieżce. Pomóż wyznaczyć odległość tej najdalszej pary.

Wejście

• Wiersze od 1: ten sam format co w „Navigation Nightmare”.

Wyjście

• Wiersz 1: całkowita odległość między najdalszą parą farm.

Przykład

Wejście 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

Wyjście 1

52

Uwagi

Wejście

Ten sam układ farm co w zadaniu 1.

Wyjaśnienie — Wyjście

Najdłuższy maraton idzie z farmy 2 przez drogi 4,1,6,3 do 5, długość $20+3+13+9+7=52$.

Autor: Brian Dean, 2004