시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 1024 MB165756747.518%

문제

판치기는 \(N\)개의 동전을 바닥에 놓고, 임의의 동전들을 뒤집는 것을 반복하여 모두 뒷면이 보이는 상태로 바꾸면 이기는 게임이다.

판치기 경력 20년에 빛나는 치훈이는 판치기 최고의 극의, "\(K\)-뒤집기"를 시전할 수 있게 되었다. "\(K\)-뒤집기"는 원하는 서로 다른 \(K\)개의 동전을 한 번에 뒤집는 능력이다.

초기 동전의 상태가 주어진다. "\(K\)-뒤집기"만 사용해 게임을 이기려면 최소 몇 번 사용해야 이길 수 있을까?

입력

첫째 줄에 \(N\), \(K\)가 주어진다.

두번째 줄에 초기 동전의 상태를 나타내는 문자열 \(S\)가 주어진다.

\(S\)의 \(i\)번째 문자가 'H'면 \(i\)번째 동전이 앞면, 'T'면 \(i\)번째 동전이 뒷면이 보이는 상태를 나타낸다.

출력

첫째 줄에 문제의 답을 출력한다.

모두 뒷면이 보이는 상태로 바꿀 수 없다면 대신 -1을 출력한다.

제한

  • 1 ≤ \(N\) ≤ 3,000
  • 1 ≤ \(K\) ≤ \(N\)

예제 입력 1

5 3
HHHHH

예제 출력 1

3

예제 입력 2

3 2
THT

예제 출력 2

-1