There is a large testing ground for robots on Mars. It is a table of n rows and m columns, the columns of which are directed from north to south, and the rows — from west to east. In each cell of the table there is an accelerator directed to one of the cardinal directions.
While in the cage, the robot can use the accelerator in it. At the same time, it enters the adjacent cell to the current cell in the direction of the accelerator and does not spend fuel. If there is no neighboring cell in the direction of the accelerator, then it cannot be used. Also, the robot may not use the accelerator and move to any of the neighboring cells, spending one liter of fuel.
Today the robot was given the following task: it needs to get from the first cell of the first column to the last cell of the last column. Write a program that will determine what is the minimum amount of fuel he will need to spend for this.
The figure below shows the polygon defined in the example. Accelerators are shown as arrows. The cells are shaded, which are optimal for the robot to pass through. The accelerators used by the robot are shown with thick arrows.
Input
The first line of the input contains two numbers n and m — the length of the polygon from north to south and from west to east ( 1 ≤ n , m ≤ 20 ).
The next n lines contain m Latin letters each describing the directions of the accelerators in the next line. The letter corresponds to the direction of the accelerator: N — north, W — west, S — south, E — to the East. Rows are numbered from north to south and columns from west to east. Thus, the direction to the north corresponds to the decrease in the line number, the direction to the south — increasing line number, west direction — decrementing the column number, and the direction to the east — increasing the column number.
Imprint
Print a single integer — the minimum number of liters of fuel that the robot must spend in order to complete the task.
Examples
| # |
Input |
Output |
| 1 |
5 3
SSN
NSN
SWN
SWE
ENS |
2 |