Tras oír sobre la epidemia de obesidad en EE. UU., Farmer John quiere más ejercicio para sus vacas y organiza un maratón bovino. La ruta incluye dos granjas y un camino de una secuencia de carreteras entre ellas. Para darles el máximo ejercicio busca las dos granjas más alejadas del mapa, midiendo distancia por la longitud total de las carreteras del camino. Ayuda a hallar la distancia de ese par más lejano.

Entrada

• Líneas desde 1: mismo formato que «Navigation Nightmare».

Salida

• Línea 1: un entero, distancia entre el par de granjas más lejano.

Ejemplos

Entrada 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

Salida 1

52

Nota

Entrada

La misma disposición de granjas que en el problema 1.

Explicación — Salida

El maratón más largo va de la granja 2 por las carreteras 4,1,6,3 a la 5, con longitud $20+3+13+9+7=52$.

Autor: Brian Dean, 2004