Nghe về dịch béo phì ở Mỹ, Farmer John muốn bò vận động nhiều hơn và quyết định tổ chức marathon bò. Tuyến gồm hai trang trại và đường đi là chuỗi đường giữa chúng. Để vận động tối đa, ông tìm hai trại xa nhau nhất trên bản đồ, khoảng cách đo bằng tổng chiều dài đường trên đường đi giữa hai trại. Giúp tính khoảng cách cặp xa nhất ấy.

Dữ liệu vào

• Các dòng từ 1: cùng định dạng với «Navigation Nightmare».

Dữ liệu ra

• Dòng 1: số nguyên chỉ khoảng cách cặp trại xa nhất.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

52

Ghi chú

Dữ liệu vào

Cùng bố trí trại như bài 1.

Giải thích — Dữ liệu ra

Marathon dài nhất từ trại 2 qua các đường 4,1,6,3 tới 5, dài $20+3+13+9+7=52$.

Tác giả: Brian Dean, 2004