לאחר ששמע על מגפת ההשמנה בארה״ב, 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

Note

קלט

אותו סידור חוות כמו בבעיה 1.

הסבר — פלט

המרתון הארוך ביותר מחווה 2 דרך הכבישים 4,1,6,3 לחווה 5, באורך $20+3+13+9+7=52$.

מחבר: Brian Dean, 2004