Problem D
The Photographer

A photographer has taken many nice photographs with his digital camera, and wants to transfer them to his computer. The pictures were taking with different rotations of the camera, so they may be rotated. We call the four possible rotations a photo can have up (upp), right (höger), down (ner) and left (vänster), where up is the correct rotation. The computer can rotate the picture by $90^\circ $ clockwise. The following figure shows how the picture will be rotated.

The photographer thinks it’s very boring to rotate photos, and decides to make it into a game. He will choose a positive integer $k$ and decides that the only way he can rotate photos is by rotating a segment of exactly $k$ adjacent photos from the list at the same time. More specifically, assume that the photographs has $N$ pictures called $a_1, a_2, \dots , a_ N$. The photographer can now choose an index $i$ ($1 \leq i \leq N-k+1$) and the pictures $a_ i, a_{i+1}, \dots , a_{i+k-1}$ will then be rotated clockwise once. We call this an operation.

The goal of the game is to turn all the photos correctly using as few operations as possible. Write a program that computes the smallest number of operations he needs.

Input

On the first line you can find two integers $N$ and $k$ ($1 \leq k \leq N \leq 100\, 000$), the number of photos and the number of photos he rotates at the same time.

On the second line you will find $N$ characters representing how the photos are rotated in the beginning U for up, H for right, N for down and V for left.

Output

Output the smallest number of operations he needs. If it cannot be done, output $-1$.

Scoring

Your program will be tested on $10$ different test data groups. For each group that your progrma pass, you get $10$ points.

• In test data groups worth $10$ points, $N$ will be at most $10$.

• In test data groups worth an additional $40$ points, $N$ will be at most $5\, 000$.

Explanation of Sample 1

One possible optimal solution is the following one. Rotate the photos on position $3-4$ three times to get the rotations UVVU. Then rotate the photos on position $2-3$ once, and you are done using 4 operations.

4 2
UVUH

4

8 5
HUNVVNVH

9

5 2
UUUUV

-1