Problem Description

You live in a city with a grid-like structure, where there are many roads extending very long in the north-south direction and many roads extending very long in the east-west direction. The distance between two adjacent north-south roads is 1 km, and the distance between two adjacent east-west roads is also 1 km.

There is one city hall in this city. The intersection where the city hall is located is represented as $(0, 0)$. An intersection in this city is represented by two integers $i$ and $j$ as intersection $(i, j)$. That is, intersection $(i, j)$ is the intersection that is $i$ km east (or $-i$ km west if $i < 0$) and $j$ km north (or $-j$ km south if $j < 0$) from intersection $(0, 0)$.

The city hall has a dog named Joy. Joy has planned a $K$-day walking schedule. The schedule is as follows:

• On the morning of the first day of the $K$ days, Joy is at intersection $(0, 0)$. Joy marks intersection $(0, 0)$. No other intersections are marked by Joy.
• Each day during the $K$ days, Joy goes for a walk in the afternoon. Each day's walk consists of $N$ steps. In each step, Joy moves from one intersection to an adjacent intersection and marks the destination. Joy's movement pattern is the same every day.
• After the afternoon walk, Joy sleeps at the current intersection until the next morning. The city hall is discussing Joy's territory formed by the $K$-day walking schedule. A square enclosed by four intersections $(a, b)$, $(a + 1, b)$, $(a + 1, b + 1)$, and $(a, b + 1)$ belongs to Joy's territory if Joy has marked each of these four intersections at least once.

You are to write a program that calculates the number of squares that belong to Joy's territory from Joy's walking schedule.

The roads in this city are very long, and there are enough roads in both the north-south and east-west directions, so Joy will never reach the end of a road or the edge of the city during the walk.

Input Format

Read the following input from the standard input:

• The first line contains two integers $N$ and $K$ separated by a space. This indicates that each day's walk consists of $N$ steps and the walking plan spans $K$ days.
• The second line contains a string $S$ of length $N$. The $p$-th character ($1 \leq p \leq N$) of the string $S$, $C_p$, is one of E, N, W, S, representing the following:
• E means moving to the adjacent intersection to the east in the $p$-th step.
• N means moving to the adjacent intersection to the north in the $p$-th step.
• W means moving to the adjacent intersection to the west in the $p$-th step.
• S means moving to the adjacent intersection to the south in the $p$-th step.

Output Format

Output the number of squares that belong to Joy's territory on one line to the standard output.

Sample Input and Output

Sample Input #1

12 1
EENWSEEESWWS

Sample Output #1

3

Sample Input #2

12 2
EENWSEEESWWS

Sample Output #2

7

Sample Input #3

7 1
ENNWNNE

Sample Output #3

0

Sample Input #4

16 5
WSESSSWWWEEENNNW

Sample Output #4

21

Notes/Hints

Task

Given Joy's walking schedule, create a program to find the number of squares that belong to Joy's territory.

Constraints

All input data satisfies the following conditions:

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

Subtasks

Subtask 1 [5 points]

Satisfies the following conditions:

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

Subtask 2 [10 points]

• $K = 1$.

Subtask 3 [23 points]

• $N \leq 50$.

Subtask 4 [62 points]

No additional constraints.

见题面 Input 部分

见题面 Output 部分