Problem Description
Benson lives on an island. The island has a field, which can be described as a rectangle of cells with N rows and M columns. The field is surrounded by water.
Alligators like to bask under the sun in the field, and due to their territorial nature, at most 1 alligator will be in each cell.
Benson does not like the alligators, and hence want to drive them away.
Benson knows that alligators hate nuts, and hence he will throw nuts at the alligators. He can only throw nuts at one alligator at a time.
When a a nut is thrown at an alligator, the alligator becomes frightened and runs in a straight line, until it is out of the field and in the water.
For every alligator, there is a direction that it will run in when it becomes frightened. This direction is parallel to the sides of the field.
If there is an alligator in the path of a frightened alligator, all the alligators will attack Benson. Benson will not throw a nut at an alligator
until the previous alligator is in the water. Help Benson find the maximum number of alligators that he can safely drive away from the field.
Input
The first line contains two integers N and M, the size of the field.
The following N lines contain M characters each.
If the character is ., then there is no alligator in that cell.
Otherwise, there is a alligator in the cell. The character denotes which direction the alligator in that cell will run in when it gets frightened.
N - North, S - South, W - West, E - East.
Output
Output a single integer, the maximum number of crocodiles that can be driven away.
Limits
Subtask 1 (30%): 1 ≤ N, M ≤ 30.
Subtask 2 (30%): 1 ≤ N, M ≤ 500.
Subtask 3 (40%): 1 ≤ N, M ≤ 2000.
Subtask 4 (0%): Sample Testcases
Sample Testcase 1
Input
1 5
WN.SE
Output
4
Sample Testcase 2
Input
1 3
E.W
Output
0
Sample Testcase 3
Input
3 4
.N.W
WWSS
EWEW
Output
4