Fotografen

A photographer took many nice photos with a digital camera and connects it to a computer to transfer them. The camera was held at different angles for each shot, so some photos are rotated. The four possible rotations are called up, right, down, and left, where up means the side that points up in the picture. A photo is correct when it is rotated up. The computer shows the photos in a list and has a function that rotates one photo 90 degrees clockwise. The rotation order is shown below.

How a photo is rotated

The photographer finds rotating photos one by one boring, so turns it into a game. The photographer picks a positive integer $k$. The only way to rotate photos is to select exactly $k$ adjacent photos from the list and rotate all of them at once. Formally, there are $N$ photos $a_1, a_2, \dots, a_N$. The photographer picks an index $i$ ($1 \leq i \leq N-k+1$), and photos $a_i, a_{i+1}, \dots, a_{i+k-1}$ are rotated 90 degrees clockwise. This is one operation.

The goal is to make every photo upright with as few operations as possible. Write a program that computes the minimum number of operations needed.

The first line contains two integers $N$ and $k$ ($1 \leq k \leq N \leq 100\,000$), the total number of photos and the number of photos that must be rotated together.

The second line contains $N$ characters that give the starting rotation of the photos: U for up, H for right, N for down, and V for left.

Print the minimum number of operations needed. If it is impossible to make all photos upright, print $-1$.

One possible optimal solution: rotate positions 3-4 three times to get UVVU, then rotate positions 2-3 once to get UUUU. This uses four operations in total.