21516번 - Робинзон и крокодилы 다국어

문제

Робинзон живет на острове, который представляет собой прямоугольник размером $n \times m$ клеток.

На остров Робинзона выползли погреться на солнышке и задремали несколько крокодилов. Робинзон хочет прогнать неприятных соседей, не поднимая шума. Для этого он кидает в дремлющих крокодилов орехи.

В каждой клетке острова находится не более одного крокодила. Напуганный орехом крокодил быстро бежит строго по прямой, пока не окажется в воде. Для каждого крокодила известно направление, в котором он побежит, если его напугать. Направления, в которых будут убегать крокодилы, параллельны сторонам острова.

Если на пути напуганного крокодила окажется другой крокодил, то, столкнувшись, они разозлятся, и нападут на Робинзона. Поэтому надо тщательно выбирать очередного крокодила, чтобы на его пути были только пустые клетки.

Робинзон не кидает очередной орех, пока предыдущий крокодил не окажется в воде.

Требуется написать программу, определяющую максимальное количество крокодилов, которых можно прогнать, не разозлив их.

입력

В первой строке входного файла записаны числа $n$ и $m$ --- размеры острова с севера на юг и с запада на восток. Последующие $n$ строк по $m$ символов в каждой описывают текущее расположение крокодилов на острове. Если клетка свободна, то она обозначается точкой <<.>>, а если там находится крокодил, то в ней указано направление, в котором побежит этот крокодил. Направления обозначаются буквами: <<N>> --- север, <<S>> --- юг, <<E>> --- восток, <<W>> --- запад.

출력

Выходной файл должен содержать одно число --- максимальное количество крокодилов, которых можно прогнать, не разозлив.

제한

• 1ドル \le n,m \le 2000$

힌트

Рисунок к третьему примеру: