사진사

한 사진사가 디지털카메라로 멋진 사진을 많이 찍은 뒤, 사진을 전송하기 위해 카메라를 컴퓨터에 연결한다. 사진을 찍을 때 카메라의 방향이 제각각이었기 때문에 현재 일부 사진은 회전되어 있다. 사진이 가질 수 있는 네 가지 회전 방향을 위쪽, 오른쪽, 아래쪽, 왼쪽이라고 부르며, 이는 사진에서 위를 향하는 쪽에 해당하는 변으로 정의한다. 사진이 위쪽으로 회전되어 있으면 올바른 방향을 향하고 있다. 컴퓨터는 사진을 목록으로 표시하며, 사진 하나를 시계 방향으로 $90^\circ$ 회전하는 기능이 있다. 따라서 회전은 다음 순서로 이루어진다:

사진이 회전하는 방식

사진사는 사진을 회전하는 일이 지루해 보인다고 생각하여, 이를 재미있는 게임으로 만들기로 한다. 사진사는 양의 정수 $k$을 선택하고, 사진을 회전하는 유일한 방법은 목록에서 서로 인접한 사진을 정확히 $k$개 선택하여 이 사진들을 모두 동시에 회전하는 것으로 정한다. 형식적으로 사진사는 $N$개의 사진을 가지고 있으며, 이를 $a_1, a_2, \dots a_N$라고 하자. 이제 사진사는 인덱스 $i$ ($1 \leq i \leq N-k+1$)를 선택할 수 있고, 그러면 사진 $a_i, a_{i+1}, ... , a_{i+k-1}$가 시계 방향으로 $90^\circ$ 회전한다. 이를 하나의 연산이라고 부른다.

게임의 목표는 가능한 한 적은 연산으로 모든 사진이 올바른 방향을 향하게 하는 것이다. 필요한 연산 횟수의 최솟값을 계산하는 프로그램을 작성하라.

채점

여러 테스트 케이스 그룹으로 해답을 테스트한다. 한 그룹에서 점수를 받으려면 해당 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ |$10$| $N \leq 10$

$2$ |$40$| $N \leq 5000$

$3$ |$50$| 추가 제한 없음.

첫째 줄에 두 정수 $N$와 $k$ ($1 \leq k \leq N \leq 4 \cdot 10 ^5$)가 주어진다. 각각 전체 사진의 수와 동시에 회전해야 하는 사진의 수를 나타낸다.

둘째 줄에는 사진들의 초기 회전 방향을 나타내는 $N$개의 문자가 주어진다. 위쪽은 U, 오른쪽은 H, 아래쪽은 N, 왼쪽은 V로 나타낸다.

필요한 연산 횟수의 최솟값을 출력한다. 모든 사진이 올바른 방향을 향하게 하는 것이 불가능하면 $-1$을 출력한다.

가능한 최적해 중 하나는 다음과 같다. 위치 3-4에서 세 번 회전하여 UVVU를 만들고, 이어서 위치 2-3에서 한 번 회전하여 최종적으로 UUUU를 만들면, 총 네 번의 연산을 수행하여 완료된다.