Hoof, Scissors, Paper

You may have played "Rock, Paper, Scissors" before. In this problem, the game is popular among cows - only its name has changed to "Hoof, Scissors, Paper". The rules are analogous to the classic game:

• Hoof beats Scissors.
• Scissors beats Paper.
• Paper beats Hoof.

If both cows show the same gesture, the round is a tie. Farmer John (FJ) and Bassie will play for \(N\) rounds. Bassie already knows FJ's gestures for each round. However, Bassie is lazy and is willing to change her gesture at most \(K\) times throughout the game.

Your task is to help Bassie determine the maximum number of rounds she can win.

Formally, let FJ's gesture for round \(i\) be given. Bassie may choose a fixed gesture for a contiguous block of rounds, but she is allowed to switch her chosen gesture at most \(K\) times (resulting in \(K+1\) segments). In each round, Bassie wins if her gesture is the winning counter to FJ's gesture. The winning rules can be summarized in latex as follows:

[ \text{win}(g) = \begin{cases} 2, &\text{if } g = 0 \quad (\text{FJ plays Hoof, Bassie must play Paper})\ 0, &\text{if } g = 1 \quad (\text{FJ plays Scissors, Bassie must play Hoof})\ 1, &\text{if } g = 2 \quad (\text{FJ plays Paper, Bassie must play Scissors}) \end{cases} ]

Note that we encode the gestures as follows: 0 for Hoof (H), 1 for Scissors (S), and 2 for Paper (P). FJ's input will be provided as characters 'H', 'S', or 'P', and Bassie must choose her gestures accordingly.

inputFormat

The first line contains two integers \(N\) and \(K\) (where \(1 \leq N \leq 10^5\) and \(0 \leq K \leq N\)), representing the number of rounds and the maximum number of times Bassie can change her gesture.

The next \(N\) lines each contain a single character, which is either 'H', 'S', or 'P'. Each character represents FJ's gesture in that round.

outputFormat

Output a single integer: the maximum number of rounds Bassie can win if she optimally chooses when to change her gesture.

sample

5 2
P
P
H
S
P

4