Mieszkasz w mieście, w którym wiele bardzo długich dróg biegnących z północy na południe przecina wiele bardzo długich dróg biegnących ze wschodu na zachód. Odległość między dwiema sąsiednimi drogami biegnącymi z północy na południe wynosi 1 km. Także odległość między dwiema sąsiednimi drogami biegnącymi ze wschodu na zachód wynosi 1 km.

W mieście jest jeden ratusz. Skrzyżowanie, przy którym się znajduje, oznaczamy przez $(0,0)$. Każde skrzyżowanie w mieście można oznaczyć parą liczb całkowitych $i,j$ jako $(i,j)$. Jest to skrzyżowanie położone $i$ km na wschód od $(0,0)$ (jeśli $i<0$, to $-i$ km na zachód) oraz $j$ km na północ (jeśli $j<0$, to $-j$ km na południe).

W ratuszu mieszka pies o imieniu ジョイ君. Zaplanował on spacery na $K$ dni w następujący sposób.

• Rano pierwszego z $K$ dni ジョイ君 znajduje się na skrzyżowaniu $(0,0)$ i je oznacza. Żadne inne skrzyżowanie nie jest jeszcze przez niego oznaczone.
• W południe każdego z $K$ dni wychodzi na spacer. Jeden spacer składa się z $N$ kroków. W każdym kroku przechodzi ze skrzyżowania na sąsiednie skrzyżowanie i oznacza miejsce, do którego dotarł. Sposób poruszania się podczas każdego spaceru jest taki sam, niezależnie od dnia.
• Po zakończeniu spaceru w południe śpi na skrzyżowaniu, na którym się znajduje, aż do następnego ranka.

W ratuszu rozmawia się o terytorium, jakie ジョイ君 wyznaczy swoimi spacerami w ciągu $K$ dni. Jeśli każde z czterech skrzyżowań $(a,b)$, $(a+1,b)$, $(a+1,b+1)$ i $(a,b+1)$ zostało przez niego oznaczone co najmniej raz, to kwartał ograniczony tymi czterema skrzyżowaniami należy do jego terytorium.

Masz napisać program, który na podstawie planu spacerów ジョイ君 obliczy liczbę kwartałów należących do jego terytorium.

Drogi w tym mieście są bardzo długie i jest ich wystarczająco wiele w obu kierunkach, więc podczas spacerów ジョイ君 nigdy nie dotrze do końca drogi ani do granicy miasta.

Zadanie

Napisz program, który na podstawie danego planu spacerów ジョイ君 obliczy liczbę kwartałów należących do jego terytorium.

Wejście

Wczytaj następujące dane ze standardowego wejścia.

• Pierwszy wiersz zawiera dwie liczby całkowite $N,K$, oddzielone spacją. Oznaczają one, że każdy spacer składa się z $N$ kroków, a plan obejmuje $K$ dni.

• Drugi wiersz zawiera napis $S$ długości $N$. Jego $p$-ty znak od lewej, $C_p$ ($1\le p\le N$), jest jednym ze znaków E, N, W, S. Znaki te mają następujące znaczenie:

  • Jeśli $C_p$ to E, w $p$-tym kroku pies przechodzi na sąsiednie skrzyżowanie na wschodzie.
  • Jeśli $C_p$ to N, w $p$-tym kroku pies przechodzi na sąsiednie skrzyżowanie na północy.
  • Jeśli $C_p$ to W, w $p$-tym kroku pies przechodzi na sąsiednie skrzyżowanie na zachodzie.
  • Jeśli $C_p$ to S, w $p$-tym kroku pies przechodzi na sąsiednie skrzyżowanie na południu.

Sąsiadami skrzyżowania $(i,j)$ na wschodzie, północy, zachodzie i południu są odpowiednio skrzyżowania $(i+1,j)$, $(i,j+1)$, $(i-1,j)$ i $(i,j-1)$.

Wyjście

Wypisz w jednym wierszu na standardowe wyjście liczbę kwartałów należących do terytorium ジョイ君.

Ograniczenia

Wszystkie dane wejściowe spełniają następujące warunki.

• $1\le N\le 100\,000$.
• $1\le K\le 1\,000\,000\,000$.

Podzadania

Podzadanie 1 [5 punktów]

Spełnione są następujące warunki.

• $N\le 50$.
• $K=1$.

Podzadanie 2 [10 punktów]

• $K=1$.

Podzadanie 3 [23 punkty]

• $N\le 50$.

Podzadanie 4 [62 punkty]

Brak dodatkowych ograniczeń.

Przykład

Wejście 1

12 1
EENWSEEESWWS

Wyjście 1

3

Uwagi

W tym przykładzie spacery odbywają się przez jeden dzień. Pierwszego dnia ジョイ君 wyrusza z ratusza i porusza się tak, jak pokazano poniżej.

Czarne kółka oznaczają skrzyżowania oznaczone przez ジョイ君, białe kółka — skrzyżowania, których nie oznaczył, podwójne kółko — skrzyżowanie z ratuszem, a liczby — poszczególne kroki.

Trasa przemieszczania się ジョイ君

W przykładzie 1 do terytorium ジョイ君 należą trzy kwartały zaznaczone kreskowaniem na poniższym rysunku.

Terytorium ジョイ君 w przykładzie 1

Wejście 2

12 2
EENWSEEESWWS

Wyjście 2

7

Uwagi

W przykładzie 2 spacery odbywają się przez dwa dni. Trasa każdego dnia jest taka sama jak w przykładzie 1. Po zakończeniu spacerów do terytorium ジョイ君 należy siedem kwartałów zaznaczonych kreskowaniem na poniższym rysunku.

Terytorium ジョイ君 w przykładzie 2

Zauważ, że przykład 2 nie spełnia ograniczeń podzadań 1 i 2.

Wejście 3

7 1
ENNWNNE

Wyjście 3

0

Uwagi

W przykładzie 3 żaden kwartał nie należy do terytorium ジョイ君.

Wejście 4

16 5
WSESSSWWWEEENNNW

Wyjście 4

21

Uwagi

Zauważ, że przykład 4 nie spełnia ograniczeń podzadań 1 i 2.