저녁 식사

저녁을 먹으러 가는 길에, 참가자들이 곱슬 감자튀김을 받기 위해 줄을 서 있다. $N$ ($1 \le N \le 100$)명의 참가자가 식당에 들어가려고 한 줄로 서 있다.

각 참가자는 오직 두 가지 언어 중 하나, 즉 Gnold 또는 Helpfile로만 프로그래밍한다. 프로그래머들은 자신과 다른 언어를 쓰는 사람 옆에 서 있는 것을 싫어하며, 오직 $K$ ($1 \le K \le 6$)명 이상으로 이루어진 그룹일 때만 식당에 들어간다.

닥터 V는 다음 과정을 반복한다.

• 줄에서 같은 언어를 쓰면서 서로 인접해 서 있는 참가자를 $K$명 이상 골라, 그 그룹을 저녁 식사에 보낸다.
• 남은 참가자들은 빈자리를 메우며, 그 결과 같은 언어를 쓰는 참가자들이 서로 붙게 될 수 있다.

처음 줄 상태가 주어질 때, 모든 참가자가 저녁을 먹으러 갈 수 있는가? 갈 수 있다면, 저녁 식사에 보내야 하는 그룹 수의 최솟값은 얼마인가?

첫째 줄에 두 정수 $N$과 $K$가 주어진다.

둘째 줄에 줄의 맨 앞부터 맨 뒤까지를 나타내는 $N$개의 문자가 주어진다. H는 Helpfile 프로그래머를, G는 Gnold 프로그래머를 뜻한다.

저녁 식사에 보내는 그룹 수의 최솟값을 한 줄에 출력한다. 모든 참가자가 저녁을 먹으러 갈 수 없다면 대신 -1을 출력한다.

예를 들어 일곱 명의 참가자가 GHHGHHG 순서로 서 있고, 두 명 이상씩 그룹을 지어 저녁을 먹으러 간다고 하자. 먼저 앞쪽의 H 두 명을 보내면 GGHHG가 남고, 이어서 남은 H 두 명을 보내면 GGG가 남으며, 마지막으로 G 세 명을 보낸다. 총 세 그룹을 보내게 된다.