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

В городе есть одна мэрия. Обозначим перекрёсток, на котором она находится, через $(0,0)$. Каждый перекрёсток города обозначается парой целых чисел $(i,j)$. А именно, перекрёсток $(i,j)$ находится на $i$ км восточнее перекрёстка $(0,0)$ (при $i<0$ — на $-i$ км западнее) и на $j$ км севернее него (при $j<0$ — на $-j$ км южнее).

В мэрии живёт собака по имени ジョイ君. Она составила план прогулок на $K$ дней. План выглядит следующим образом.

• Утром первого из $K$ дней ジョイ君 находится на перекрёстке $(0,0)$ и ставит на нём метку. Ни на одном другом перекрёстке её меток нет.
• Днём каждого из $K$ дней она выходит на прогулку. Каждая прогулка состоит из $N$ шагов. На каждом шаге она переходит с одного перекрёстка на соседний и ставит метку на перекрёстке, куда пришла. Последовательность перемещений днём одинакова во все дни.
• Закончив дневные перемещения, она спит на текущем перекрёстке до утра следующего дня.

В мэрии обсуждают территорию ジョイ君, которая образуется за $K$ дней прогулок. Если ジョイ君 хотя бы один раз пометила каждый из четырёх перекрёстков $(a,b),(a+1,b),(a+1,b+1),(a,b+1)$, то квартал, ограниченный этими четырьмя перекрёстками, принадлежит её территории.

Вам поручено написать программу, которая по плану прогулок ジョイ君 вычисляет количество кварталов, принадлежащих её территории.

Дороги в этом городе очень длинные, и дорог в обоих направлениях достаточно много, поэтому во время прогулок ジョイ君 никогда не дойдёт до конца дороги или края города.

Задание

Напишите программу, которая по плану прогулок ジョイ君 находит количество кварталов, принадлежащих её территории.

Входные данные

Прочитайте следующие данные из стандартного ввода.

• Первая строка содержит два целых числа $N,K$, разделённых пробелом. Они означают, что каждая прогулка состоит из $N$ шагов, а план рассчитан на $K$ дней.

• Вторая строка содержит строку $S$ длины $N$. Её $p$-й слева символ $C_p$ ($1\le p\le N$) — один из символов E, N, W, S. Эти символы имеют следующий смысл.

  • Если $C_p$ равен E, на $p$-м шаге собака переходит на соседний перекрёсток к востоку.
  • Если $C_p$ равен N, на $p$-м шаге собака переходит на соседний перекрёсток к северу.
  • Если $C_p$ равен W, на $p$-м шаге собака переходит на соседний перекрёсток к западу.
  • Если $C_p$ равен S, на $p$-м шаге собака переходит на соседний перекрёсток к югу.

  Для перекрёстка $(i,j)$ соседние перекрёстки к востоку, северу, западу и югу имеют координаты $(i+1,j)$, $(i,j+1)$, $(i-1,j)$ и $(i,j-1)$ соответственно.

Выходные данные

Выведите в стандартный вывод одной строкой количество кварталов, принадлежащих территории ジョイ君.

Ограничения

Все входные данные удовлетворяют следующим условиям.

• $1\le N\le100\,000$.
• $1\le K\le1\,000\,000\,000$.

Подзадачи

Подзадача 1 [5 баллов]

Выполняются следующие условия.

• $N\le50$.
• $K=1$.

Подзадача 2 [10 баллов]

• $K=1$.

Подзадача 3 [23 балла]

• $N\le50$.

Подзадача 4 [62 балла]

Дополнительных ограничений нет.

Примеры

Входные данные 1

12 1
EENWSEEESWWS

Выходные данные 1

3

Примечание

В этом примере прогулки продолжаются один день. В первый день ジョイ君 выходит из мэрии и движется, как показано на рисунке ниже.

Чёрные кружки обозначают помеченные перекрёстки, белые — непомеченные, двойной кружок — перекрёсток с мэрией, а числа — соответствующие шаги.

Маршрут ジョイ君

В примере 1 территории ジョイ君 принадлежат три квартала, заштрихованные на рисунке ниже.

Территория ジョイ君 в примере 1

Входные данные 2

12 2
EENWSEEESWWS

Выходные данные 2

7

Примечание

В примере 2 прогулки продолжаются два дня. Маршрут каждого дня совпадает с маршрутом в примере 1. После завершения прогулок территории ジョイ君 принадлежат семь кварталов, заштрихованных на рисунке ниже.

Территория ジョイ君 в примере 2

Обратите внимание, что пример 2 не удовлетворяет ограничениям подзадач 1 и 2.

Входные данные 3

7 1
ENNWNNE

Выходные данные 3

0

Примечание

В примере 3 территории ジョイ君 не принадлежит ни одного квартала.

Входные данные 4

16 5
WSESSSWWWEEENNNW

Выходные данные 4

21

Примечание

Обратите внимание, что пример 4 не удовлетворяет ограничениям подзадач 1 и 2.