Description

You might have played “Rock, Paper, Scissors.” This game is also popular among cows, but it is called “Hoof, Scissors, Paper.”

The rules of “Hoof, Scissors, Paper” are very similar to “Rock, Paper, Scissors.” Two cows count to three, then show one of the gestures representing hoof, scissors, or paper. Hoof beats scissors, scissors beat paper, and paper beats hoof. In particular, if both cows show the same gesture, it is a tie.

Now FJ and Bessie will play $N$ rounds. Bessie has already predicted FJ’s gesture in each round. However, Bessie is lazy and wants to change her gesture at most $K$ times.

Please help Bessie determine the maximum number of rounds she can win.

Input Format

The first line contains two integers $N,K$ ($1 \leq N \leq 10^5$, $0 \leq K \leq 20$).

The next $N$ lines each contain one letter, representing FJ’s gesture in that round. H stands for hoof (Hoof), S stands for scissors (Scissors), and P stands for paper (Paper).

Output Format

Output a single integer, the maximum number of rounds Bessie can win if she can change her gesture at most $K$ times.

5 1
P
P
H
P
S

4

Hint

Translated by ChatGPT 5