Dinner

Interview

Time limit1sMemory limit128 MB

Summary

Given a line of G and H programmers, repeatedly remove a run of at least K equal letters; find the minimum number of removals to clear the line, or -1.

Level: Medium7 of 10
Topics: Dynamic programming, Intervals, Brute force, String
Solved: No attempts yet

Problem

On the way to dinner, the competitors are lining up for their delicious curly fries. $N$ ( $1 \le N \le 100$ ) competitors have lined up single-file to enter the cafeteria.

Each competitor programs in exactly one of only two languages: Gnold or Helpfile. Programmers hate standing in line next to programmers who use a different language, and they will only enter the cafeteria as a group of at least $K$ ( $1 \le K \le 6$ ) competitors.

Doctor V repeats the following step:

Pick $K$ or more competitors who use the same language and are standing next to each other in line, and send that group to dinner.
The remaining competitors close the gap, which may put competitors who use the same language next to each other.

Given the initial line-up, can every competitor go to dinner? If so, what is the minimum number of groups that must be sent to dinner?

Input

The first line contains two integers $N$ and $K$ .

The second line contains $N$ characters describing the line from front to back, where H is a Helpfile programmer and G is a Gnold programmer.

Output

Output, on one line, the minimum number of groups that are sent to dinner. If not every competitor can go to dinner, output -1 instead.

Note

For example, suppose seven competitors stand in the order GHHGHHG and go to dinner in groups of at least two. First send the front pair of Hs, leaving GGHHG; then send the other pair of Hs, leaving GGG; finally send the three Gs. Three groups are sent in total.

Examples1

Example 1
Input
```
7 2
GHHGHHG
```
Expected output
```
3
```