내 선물을 받아줘

욱제는 구사과의 열렬한 팬이다. 오늘 욱제는 구사과에게 선물을 전달하려고 한다. 며칠 동안 관찰한 끝에 욱제는 구사과의 이동 패턴을 모두 파악했다.

구사과가 있는 곳은 $N \times M$ 크기의 직사각형 지도로 나타낼 수 있고, 지도는 $1 \times 1$ 크기의 정사각형 칸으로 나누어져 있다. 구사과의 위치는 $(i, j)$로 나타내며, $(i, j)$는 위에서 $i$번째, 왼쪽에서 $j$번째 칸이다.

지도의 각 칸에는 N, W, E, S 중 한 문자가 쓰여 있고, 구사과는 이 문자에 따라 이동한다. 구사과가 $(i, j)$에 서 있을 때 그 칸의 문자가 N이면 $(i-1, j)$로, S이면 $(i+1, j)$로, W이면 $(i, j-1)$로, E이면 $(i, j+1)$로 순간이동한다. 구사과는 지치지 않으므로 이 이동을 끝없이 반복한다.

욱제는 구사과가 지금 어디에 있는지 모른다. 그래서 구사과가 어느 칸에서 이동을 시작하더라도 선물을 받게 되는 방법을 찾으려고 한다. 선물이 놓인 칸에 구사과가 도착하면 구사과는 항상 그 선물을 가져간다. 구사과가 시작 위치와 관계없이 항상 선물을 가져가도록 하려면 최소 몇 개의 칸에 선물을 놓아야 하는지 구하는 프로그램을 작성하시오.

첫째 줄에 지도의 세로 크기 $N$과 가로 크기 $M$이 주어진다. ($1 \le N, M \le 1\,000$, $1 < N \times M \le 1\,000\,000$)

둘째 줄부터 $N$개의 줄에 지도가 한 줄에 한 행씩 주어진다. 각 줄은 N, W, E, S로만 이루어진 길이 $M$의 문자열이다.

지도에 쓰인 대로 이동했을 때 지도를 벗어나는 경우는 없다.

첫째 줄에 선물을 놓아야 하는 칸 수의 최솟값을 출력한다.