사진작가

한 사진작가가 디지털 카메라로 좋은 사진을 많이 찍었고, 이 사진을 컴퓨터에 연결해 옮기려고 합니다. 사진마다 카메라를 든 방향이 달라서 일부 사진은 회전되어 있습니다. 가능한 회전 상태는 네 가지이며 각각 위, 오른쪽, 아래, 왼쪽이라고 부릅니다. 여기서 위는 사진 속에서 위를 향한 쪽을 뜻합니다. 사진이 위 상태이면 올바른 방향입니다. 컴퓨터는 사진을 목록으로 보여주고, 사진 한 장을 시계 방향으로 90도 회전하는 기능이 있습니다. 회전 순서는 아래 그림과 같습니다.

사진이 회전되는 방식

사진작가는 사진을 한 장씩 돌리는 일이 지루해서 이를 게임으로 만들었습니다. 사진작가는 양의 정수 $k$를 정합니다. 사진을 회전하는 방법은 목록에서 서로 붙어 있는 사진을 정확히 $k$장 골라 모두 동시에 회전하는 것뿐입니다. 형식적으로 사진이 $N$장 있고 이를 $a_1, a_2, \dots, a_N$이라고 합시다. 사진작가는 인덱스 $i$ ($1 \leq i \leq N-k+1$)를 고르고, $a_i, a_{i+1}, \dots, a_{i+k-1}$을 시계 방향으로 90도 회전합니다. 이것을 연산 한 번이라고 합니다.

목표는 가능한 적은 연산으로 모든 사진을 올바른 방향으로 만드는 것입니다. 필요한 최소 연산 횟수를 구하는 프로그램을 작성하세요.

첫 줄에 두 정수 $N$과 $k$ ($1 \leq k \leq N \leq 100\,000$)가 주어집니다. 각각 사진의 총 장수와 함께 회전해야 하는 사진의 장수입니다.

둘째 줄에는 사진의 처음 회전 상태를 나타내는 $N$개의 문자가 주어집니다. U는 위, H는 오른쪽, N은 아래, V는 왼쪽입니다.

모든 사진을 올바른 방향으로 만드는 데 필요한 최소 연산 횟수를 출력하세요. 모든 사진을 올바른 방향으로 만들 수 없으면 $-1$을 출력하세요.

최적 해의 한 예는 다음과 같습니다. 위치 3-4의 사진을 세 번 회전해 UVVU를 만들고, 위치 2-3의 사진을 한 번 회전해 UUUU를 얻습니다. 연산은 모두 4번입니다.