Робинзон живет на острове, который представляет собой прямоугольник размером \(n \times m\) клеток.
На остров Робинзона выползли погреться на солнышке и задремали несколько крокодилов. Робинзон хочет прогнать неприятных соседей, не поднимая шума. Для этого он кидает в дремлющих крокодилов орехи.
В каждой клетке острова находится не более одного крокодила. Напуганный орехом крокодил быстро бежит строго по прямой, пока не окажется в воде. Для каждого крокодила известно направление, в котором он побежит, если его напугать. Направления, в которых будут убегать крокодилы, параллельны сторонам острова.
Если на пути напуганного крокодила окажется другой крокодил, то, столкнувшись, они разозлятся, и нападут на Робинзона. Поэтому надо тщательно выбирать очередного крокодила, чтобы на его пути были только пустые клетки.
Робинзон не кидает очередной орех, пока предыдущий крокодил не окажется в воде.
Требуется написать программу, определяющую максимальное количество крокодилов, которых можно прогнать, не разозлив их.
Формат входных данных
В первой строке записаны числа \(n\) и \(m\) "— размеры острова с севера на юг и с запада на восток. Последующие \(n\) строк по \(m\) символов в каждой описывают текущее расположение крокодилов на острове. Если клетка свободна, то она обозначается точкой <<.>>, а если там находится крокодил, то в ней указано направление, в котором побежит этот крокодил. Направления обозначаются буквами: <<N>> "— север, <<S>> "— юг, <<E>> "— восток, <<W>> "— запад.
Формат входных данных
Выходной файл должен содержать одно число "— максимальное количество крокодилов, которых можно прогнать, не разозлив.
Пояснение к третьему примеру
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 1
.
|
0
|
|
2
|
1 1
W
|
1
|
|
3
|
5 7
.......
...S...
..WE...
...N...
.......
|
2
|