На правоаголна платформа составена од N x M клетки паркирани се паметни роботски коли. Во една клетка има најмногу една таква кола. Секое утро, за да може да почнат со работа тие прво треба безбедно да ја напуштат платформата извозувајќи се од неа.

Процесот на напуштање на платформата не е автоматизиран, туку Димче од контролната тераса го контролира процесот преку праќање сигнали до секој од автомобилите.

Утрово, контролната табла на терасата се расипала, па Димче на секоја кола може да и ја прати само командата „вози“, по што колата што ја добила командата почнува да вози во насока во која е позиционирана таму (кон исток, кон запад, кон север или кон југ) и се одвозува надвор од платформата преку работ, доколку патот е чист. Ако има друга кола на некоја од клетките на патот од првата тогаш ќе настане судир, а такво нешто никако не сакаме да се случи. Димче ќе ги пушта колите една по една.

Ако ви е дадена конфигурацијата на платформата, со насоката на сите поставени коли на неа, помогнете му на Димче да пушти да работат што е можно повеќе коли. Направете програма која ќе пресмета колку најмногу коли може да излезат да работат, без да се случи ниту еден судир.

Влез

Во првиот ред се дадени два цели броеви N и M (1 ≤ N, M ≤ 2000).
Следните N редови содржат по М знаци кои ја опишуваат платформата. Знакот ‘.’ означува празна клетка. Во спротивно, клетката содржи еден од знаците ‘N’, ‘S’, ‘W’, ‘E’ кој означува во која насока ќе почне да вози колата што е таму, откако ќе добие команда „вози“. Притоа ‘N’ е ознака за север, ‘S’ за југ, ‘W’ за запад и ‘E’ за исток.

Забелешка.
Во подзадача 1, за 17 поени: N, M ≤ 30.
Во подзадача 2, за 30 поени: N, M ≤ 500.
Во подзадача 3, за 53 поени: N, M ≤ 2000.

Излез

Во првиот и единствен ред отпечатете го бараниот резултат.

Ограничувања

Временско ограничување: 800 milliseconds
Мемориско ограничување: 256 megabytes

Примери

влез
2 4
WN.E
S.S.

излез
5

влез
3 1
S
.
N

излез
0

влез
4 3
SWS
NW.
SSE
NS.

излез
4

Објаснување на примерите: Само колите означени со задебелени букви во влезот може слободно да излезат, некои веднаш, а некои откако некои други коли претходно ќе излезат.