米国の肥満の流行を聞いた Farmer John は牛にもっと運動させるため、牛のマラソンを計画しました。コースは 2 農場と、それらを結ぶ一連の道路の道です。できる限り運動させるため、地図で最も離れた 2 農場を探します。距離は間の道の道路全長です。この最遠の農場の組の距離を求めてください。
入力
- 1 行目以降：「Navigation Nightmare」と同じ入力形式。
出力
- 1 行目：最も離れた 2 農場の距離を整数で。
入出力例
入力 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