미국의 비만 유행을 들은 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