European Junior Olympiad in Informatics 2542 is held in Arrowland. Arrowland is shaped like a grid with rows (numbered 0 through m - 1) and columns (numbered 0 through n - 1), where each cell represents a city. Let (r, c) denote the cell in row r and column c. The contestants are accommodated in the cell (0, 0) and the competition hall is in the cell (m - 1, n - 1).

A strange tourist attraction of Arrowland is that some cities have giant arrows. Even stranger, these arrows can only be rotated clockwise by 90 degrees at a time. Each arrow initially points to either North, East, South or West. Because of the host country's name, the EJOI organisers want to make use of the arrows.

The contestants will blindly follow the arrows, regardless of their current position. From each city, they simply move to the adjacent city pointed to by the arrow. If they enter a city with no arrow or if they leave Arrowland, they will just stay there and will never reach the competition hall. Since the EJOI organisers want the contestants to arrive to the hall from their accommodation (cell (0, 0)), they might have to rotate some arrows. Help them determine the minimum number of rotations required to achieve their goal, or tell them that the contestants cannot reach the hall, regardless of the arrows' orientation.

Input

Первая строка содержит два целых числа m и n (1 ≤ ​ n, m ​ ≤ 500) - число строк и столбцов. Следующие m строк содержат по n символов,задающих изначальное направление стрелок (N - север, E - восток , S - юг, W - запад, X - нет стрелки). Последний символ последней строки (то есть символ, соответствующий залу соревнований) всегда будет X. Символ N означает направление "вверх", E означает "вправо", S означает "вниз", и W означает "влево". Каждая клетка содержит один из символов: N, E, S, W, X.

Output

Выведите минимальное число поворотов стрелок, которые нужно сделать организаторам. Если решения не существует, то выведите -1.

Объяснения к первому примеру

Оптимальное решение - изменить W в клетке (1, 2) на S, повернув стрелку три раза.

Объяснения ко второму примеру

Здесь ничего делать не нужно, участники и так доберутся до зала соревнований.

Объяснения к третьему примеру

Повернуть стрелку в клетке (0, 0) один раз (чтобы получить S), стрелку в клетке (1, 0) два раза (чтобы получить E), и стрелку в клетке (2, 1) один раз (чтобы получить E).