Dopo aver sentito dell’epidemia di obesità negli USA, Farmer John vuole far muovere di più le mucche e organizza una maratona bovina. Il percorso include due fattorie e un cammino di una sequenza di strade fra loro. Per il massimo esercizio cerca le due fattorie più lontane sulla mappa, misurando la distanza come somma delle lunghezze delle strade del cammino. Aiutalo a trovare la distanza della coppia più lontana.

Input

• Righe a partire dalla 1: stesso formato di «Navigation Nightmare».

Output

• Riga 1: intero, distanza fra la coppia di fattorie più lontana.

Esempi

Input 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

Output 1

52

Note

Input

Stessa disposizione delle fattorie del problema 1.

Spiegazione — Output

La maratona più lunga va dalla fattoria 2 per le strade 4,1,6,3 alla 5, con lunghezza $20+3+13+9+7=52$.

Autore: Brian Dean, 2004