DINGRP  Dinner
On the way to dinner, the CCC competitors are lining up for their delicious curly fries. The N (1 ≤ N ≤ 100) competitors have lined up singlefile to enter the cafeteria.
Doctor V, who runs the CCC, realized at the last minute that programmers simply hate standing in line next to programmers who use a different language. Thankfully, only two languages are allowed at the CCC: Gnold and Helpfile. Furthermore, the competitors have decided that they will only enter the cafeteria if they are in a group of at least K (1 ≤ K ≤ 6) competitors.
Doctor V decided to iterate the following scheme:
 He will find a group of K or more competitors who use the same language standing next to each other in line and send them to dinner.
 The remaining competitors will close the gap, potentially putting similarlanguage competitors together.
So Doctor V recorded the sequence of competitors for you. Can all the competitors dine? If so, what is the minimum number of groups of competitors to be sent to dinner?
Input
The first line contains two integers N and K.
The second line contains N characters that are the sequence of competitors in line (H represents Helpfile, G represents Gnold)
Output
Output, on one line, the single number that is the minimum number of groups that are formed for dinner. If not all programmers can dine, output 1.
Sample Input
7 2 GHHGHHG
Sample Output
3
Explanation
There are seven competitors: a Gnold programmer followed by two Helpfile programmers, followed by another Gnold programmer, followed by another two Helpfile programmers followed by a final Gnold programmer. Programmers want to go to dinner in pairs.
First send the first pair of Hs to dinner, leaving GGHHG. Then send the second pair of Hs to dinner, leaving GGG; finally, send in the group of Gs. It might be coincidental that the two pairs of Helpfile programmers entered the cafeteria successively.
hide comments
hamjosh1:
20161221 17:28:49
enjoyed :) 

Brian Bi:
20100314 20:26:00
I don't think so. 

Devil D:
20100204 08:49:54
any peculiar test case ...

Added by:  Brian Bi 
Date:  20100130 
Time limit:  0.165s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS objc PERL 6 VB.net 
Resource:  2009 Canadian Computing Competition Stage 2  Problem B 