## USACO 2017 January Contest, Gold

## Problem 2. Hoof, Paper, Scissors

Contest has ended.

**Log in to allow submissions in analysis mode**

The rules of "Hoof, Paper, Scissors" are simple. Two cows play against each-other. They both count to 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 beats 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 second 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 \leq N \leq 100,000$). Bessie, being an expert at the game, can predict each of FJ's gestures before he makes it. Unfortunately, Bessie, being a cow, is also very lazy. As a result, she tends to play the same gesture multiple times in a row. In fact, she is only willing to switch gestures at most $K$ times over the entire set of games ($0 \leq K \leq 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 FJ will be playing, please determine the maximum number of games that Bessie can win.

#### INPUT FORMAT (file hps.in):

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.

#### OUTPUT FORMAT (file hps.out):

Print the maximum number of games Bessie can win, given that she can only change gestures at most $K$ times.#### SAMPLE INPUT:

5 1 P P H P S

#### SAMPLE OUTPUT:

4

Problem credits: Mark Chen and Brian Dean