문제
농부 창호는 그의 소들이 살이 너무나도 뒤룩뒤룩 쪄서 운동을 시켜야 할 필요를 느꼈다. 그는 그의 농장에서 가장 먼 두 지점을 찾아서 그의 소들에게 매일 마라톤을 시키려고 한다. 두 지점 사이의 거리는 맨해튼 거리가 아니라, 도로를 따라갔을 때의 거리이다.
입력
입력의 첫 줄에 공백으로 구분된 두 개의 정수 N, M이 입력된다.
이후 M개의 줄에 걸쳐 도로의 정보가 입력된다.
각 줄의 첫 번째 숫자와 두 번째 숫자는 도로의 양 끝에 있는 농장의 번호이다. 세 번째 숫자는 도로의 길이를 나타내며, 네 번째 문자는 첫 번째 농장을 기준으로 두 번째 농장의 위치가 어느 방향인지 나타낸다(N은 북쪽, E는 동쪽, W는 서쪽, S는 남쪽).
출력
가장 먼 두 지점 사이의 거리를 출력한다.
예제
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
52
힌트
로그인해야 코드를 작성할 수 있어요.