Nach Berichten über die Übergewichts-Epidemie in den USA möchte Farmer John seinen Kühen mehr Bewegung verschaffen und veranstaltet einen Kuhmarathon. Die Strecke umfasst zwei Farmen und einen Weg aus aufeinanderfolgenden Straßen zwischen ihnen. Für möglichst viel Bewegung sucht er das am weitesten entfernte Farmpaar auf der Karte; die Entfernung ist die gesamte Straßenlänge des Wegs dazwischen. Hilf ihm, diese Entfernung zu bestimmen.

Eingabe

• Zeilen ab 1: gleiches Format wie „Navigation Nightmare“.

Ausgabe

• Zeile 1: ganze Zahl, Entfernung zwischen dem weitesten Farmpaar.

Beispiele

Eingabe 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

Ausgabe 1

52

Hinweis

Eingabe

Gleiche Farmanordnung wie in Aufgabe 1.

Erklärung — Ausgabe

Der längste Marathon führt von Farm 2 über die Straßen 4,1,6,3 zu Farm 5, mit Länge $20+3+13+9+7=52$.

Autor: Brian Dean, 2004