Após saber da epidemia de obesidade nos EUA, Farmer John quer mais exercício para as vacas e decidiu criar uma maratona bovina. A rota inclui duas fazendas e um caminho de uma sequência de estradas entre elas. Para maximizar o exercício procura as duas fazendas mais distantes no mapa, medindo distância pela soma das estradas do caminho. Ajude a achar a distância desse par mais distante.

Entrada

• Linhas a partir de 1: mesmo formato de «Navigation Nightmare».

Saída

• Linha 1: inteiro, distância entre o par de fazendas mais distante.

Exemplos

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

Saída 1

52

Note

Entrada

A mesma disposição de fazendas do problema 1.

Explicação — Saída

A maior maratona vai da fazenda 2 pelas estradas 4,1,6,3 até a 5, com comprimento $20+3+13+9+7=52$.

Autor: Brian Dean, 2004