Usted probablemente ha oído del juego "Roca, Piedra, Tijera". A las vacas del Granjero Juan les gusta jugar un juego similar y como son gringas lo llaman "Hoof, Paper, Scissors". ("Hoof" es Pezuña, "Paper" es Papel, "Scissors" es Tijeras).

Las reglas de "Hoof, Paper, Scissors" son simples. Dos vacas juegan una en contra de la otra. Ambas cuentan hasta tres y luego cada una hace simultaneamente un gesto que representa o Hoof, Paper, o Scissors. Hoof gana a Scissors (desde que una pezuña puede romper un par de tijeras), Scissors gana a Paper (desde que un par de tijeras puede cortar un papel), y Paper gana a Hoof (desde que una pezuña puede ser envuelta por el papel). Por ejemplo si la primera vaca hace el gesto "Hoof" y la segunda el gesto "Paper", entonces gana la segunda vaca. Por supuesto, es también posible un empate, si ambas vacas hacen el mismo gesto.

El Granjero Juan quiere jugar contra su vaca ganadora, Bessie en ~N~ juegos de "Hoof, Paper, Scissors" \((1\leN\le100,000)\). Bessie, siendo una experta en el juego, puede predecir cada uno de los gestos de GJ antes que él los haga. Desafortunadamente, Bessie, siendo una vaca, es muy floja. Como resultado, ella tiene a jugar el mismo gesto en una fila. De hecho, ella quiere cambiar únicamente gestos a lo más ~K~ veces en donde el conjunto de juegos \((0\leK\le20)\). Por ejemplo, si ~K=2~

, ella podría jugar "hoof" los primers juegos, luego cambiara a "paper" por un tiempo, luego terminar los juegos restantes jugando "hoof".

Dada la secuencia de gestos que GJ estará jugando, por favor, determine el máximo número de juegos que Bessie puede ganar.

Entrada

La primera línea del archivo de entrada contiene ~N~ y ~K~. Las ~N~ líneas restantes contienen los gestos de GJ, cada una o ~H~, ~P~, o ~S~.

Salida

Imprima el número máximo de juegos que Bessie puede ganar, dado que ella puede cambiar únicamente gestos a lo más ~K~ veces.

Ejemplo de Entrada

5 1
P
P
H
P
S

Ejemplo de Salida

4