Hoof, Paper, Scissors (Gold)

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

The rules of "Hoof, Paper, Scissors" are simple. Two cows play against each other. They both count to three, and then each one simultaneously makes a gesture that represents either a hoof, a piece of paper, or a pair of scissors. Hoof beats scissors (a hoof can smash a pair of scissors), scissors beats paper (scissors can cut paper), and paper beats hoof (the hoof can get a papercut). For example, if the first cow makes a "hoof" gesture and the second makes a "paper" gesture, the second cow wins. Both cows can also make the same gesture, in which case the game is a tie.

Farmer John wants to play $N$ games of "Hoof, Paper, Scissors" against his prize cow, Bessie ($1 \le N \le 100\,000$). Bessie is an expert at the game and can predict each of John's gestures before he makes it. Unfortunately, Bessie is a cow, so she is also very lazy. She tends to play the same gesture many times in a row. In fact, she is only willing to switch gestures at most $K$ times over the entire set of games ($0 \le K \le 20$). For example, if $K=2$, she might play "hoof" for the first few games, then switch to "paper" for a while, then finish the remaining games playing "hoof".

Given the sequence of gestures John will play, determine the maximum number of games that Bessie can win.

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

Each of the next $N$ lines contains one of John's gestures, in order. Each gesture is H (hoof), P (paper), or S (scissors).

Print the maximum number of games Bessie can win if she changes gestures at most $K$ times.