Você mora em uma cidade formada pelo cruzamento de muitas ruas muito longas na direção norte–sul com muitas ruas muito longas na direção leste–oeste. A distância entre duas ruas consecutivas na direção norte–sul é de 1 km. A distância entre duas ruas consecutivas na direção leste–oeste também é de 1 km.

Há uma prefeitura na cidade. O cruzamento onde ela fica é representado por $(0,0)$. Cada cruzamento da cidade é representado por $(i,j)$, usando dois inteiros $i,j$. Mais precisamente, o cruzamento $(i,j)$ fica $i$ km a leste de $(0,0)$ (ou $-i$ km a oeste, se $i<0$) e $j$ km ao norte (ou $-j$ km ao sul, se $j<0$).

A prefeitura cuida de um cachorro chamado ジョイ君. Ele planejou passear durante $K$ dias. O plano de passeios é o seguinte.

• Na manhã do primeiro dos $K$ dias, ジョイ君 está no cruzamento $(0,0)$ e o marca. Nenhum outro cruzamento está marcado por ele.
• Ele passeia durante o dia em cada um dos $K$ dias. Cada passeio diário consiste em $N$ passos. Em cada passo, ele se move de um cruzamento para um cruzamento vizinho e marca o destino. A sequência de movimentos realizada durante o dia é a mesma em todos os dias.
• Depois de terminar os movimentos do dia, ele dorme no cruzamento onde está até a manhã seguinte.

Na prefeitura, as pessoas estão comentando sobre o território que ジョイ君 formará ao passear durante $K$ dias. Se ele tiver marcado pelo menos uma vez cada um dos quatro cruzamentos $(a,b),(a+1,b),(a+1,b+1),(a,b+1)$, o quarteirão delimitado por eles pertence ao território de ジョイ君.

Você ficou encarregado de criar um programa que calcule, a partir do plano de passeios de ジョイ君, o número de quarteirões pertencentes ao seu território.

As ruas da cidade são muito longas e há ruas suficientes nas duas direções. Portanto, durante os passeios, ジョイ君 nunca chega ao fim de uma rua nem ao limite da cidade.

Tarefa

Dado o plano de passeios de ジョイ君, escreva um programa que determine o número de quarteirões pertencentes ao seu território.

Entrada

Leia os dados a seguir da entrada padrão.

• A primeira linha contém dois inteiros $N,K$, separados por um espaço. Isso indica que cada passeio diário consiste em $N$ passos e que o plano de passeios abrange $K$ dias.

• A segunda linha contém uma cadeia $S$ de comprimento $N$. O caractere $C_p$, na $p$-ésima posição da esquerda para a direita ($1 \le p \le N$), é um dos caracteres E, N, W, S. Eles têm os seguintes significados.

  • Se $C_p$ for E, no $p$-ésimo passo ele se move para o cruzamento vizinho a leste.
  • Se $C_p$ for N, no $p$-ésimo passo ele se move para o cruzamento vizinho ao norte.
  • Se $C_p$ for W, no $p$-ésimo passo ele se move para o cruzamento vizinho a oeste.
  • Se $C_p$ for S, no $p$-ésimo passo ele se move para o cruzamento vizinho ao sul.

Para o cruzamento $(i,j)$, os cruzamentos vizinhos a leste, ao norte, a oeste e ao sul são, respectivamente, $(i+1,j)$, $(i,j+1)$, $(i-1,j)$ e $(i,j-1)$.

Saída

Escreva na saída padrão, em uma linha, o número de quarteirões pertencentes ao território de ジョイ君.

Restrições

Todos os dados de entrada satisfazem as seguintes condições.

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

Subtarefas

Subtarefa 1 [5 pontos]

As seguintes condições são satisfeitas.

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

Subtarefa 2 [10 pontos]

• $K=1$.

Subtarefa 3 [23 pontos]

• $N \le 50$.

Subtarefa 4 [62 pontos]

Não há restrições adicionais.

Exemplos

Entrada 1

12 1
EENWSEEESWWS

Saída 1

3

Observação

Neste exemplo, o passeio dura 1 dia. No primeiro dia, ジョイ君 parte da prefeitura e se move como mostra a figura abaixo.

Os círculos pretos representam cruzamentos marcados por ジョイ君; os círculos brancos representam cruzamentos que ele não marcou; o círculo duplo representa o cruzamento onde fica a prefeitura; e os números representam os passos.

Percurso de ジョイ君

No Exemplo de Entrada 1, os 3 quarteirões hachurados na figura abaixo pertencem ao território de ジョイ君.

Território de ジョイ君 no Exemplo de Entrada 1

Entrada 2

12 2
EENWSEEESWWS

Saída 2

7

Observação

No Exemplo de Entrada 2, os passeios são realizados durante 2 dias. O percurso de cada dia é o mesmo do Exemplo de Entrada 1. Ao final dos passeios, os 7 quarteirões hachurados na figura abaixo pertencem ao território de ジョイ君.

Território de ジョイ君 no Exemplo de Entrada 2

Observe que o Exemplo de Entrada 2 não satisfaz as restrições das Subtarefas 1 e 2.

Entrada 3

7 1
ENNWNNE

Saída 3

0

Observação

No Exemplo de Entrada 3, não há quarteirões pertencentes ao território de ジョイ君.

Entrada 4

16 5
WSESSSWWWEEENNNW

Saída 4

21

Observação

Observe que o Exemplo de Entrada 4 não satisfaz as restrições das Subtarefas 1 e 2.