# #4760. [Usaco2017 Jan]Hoof, Paper, Scissors

#### 题目描述

You have probably heard of the game "Rock, Paper, Scissors". The cows like to play a similar game th
ey call "Hoof, Paper, Scissors"

The rules of "Hoof, Paper, Scissors" are simple. Two cows play against each-other. They both count t
o three and then each simultaneously makes a gesture that represents either a hoof, a piece of paper
, or a pair of scissors. Hoof beats scissors (since a hoof can smash a pair of scissors), scissors b
eats paper (since scissors can cut paper), and paper beats hoof (since the hoof can get a papercut).
For example, if the first cow makes a "hoof" gesture and the second a "paper" gesture, then the sec
ond cow wins. Of course, it is also possible to tie, if both cows make the same gesture.

Farmer John wants to play against his prize cow, Bessie, at N games of "Hoof, Paper, Scissors" (1≤N
≤100,000). Bessie, being an expert at the game, can predict each of FJ's gestures before he makes i
t. Unfortunately, Bessie, being a cow, is also very lazy. As a result, she tends to play the same ge
sture multiple times in a row. In fact, she is only willing to switch gestures at most KK times over
the entire set of games (0≤K≤20). For example, if K=2, she might play "hoof" for the first few ga
mes, then switch to "paper" for a while, then finish the remaining games playing "hoof".

essie，作为一个奶牛，非常的怠惰，无论她出什么，都喜欢连续的出，最多变化K次(K<=20)，也就是说，对于她

Given the sequence of gestures FJ will be playing, please determine the maximum number of games that
Bessiecan win.

#### 输入格式

The first line of the input file contains N and K.

The remaining N lines contains FJ's gestures, each either H, P, or S

#### 输出格式

Print the maximum number of games Bessie can win, given that she can only change gestures at most KK times.

5 1
P
P
H
P
S

4