بعد سماعه عن وباء السمنة في الولايات المتحدة، يريد 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