题目描述

两名选手进行 $N$ 轮魔法对决。三种魔法分别用 H、S、P 表示，并且 H 战胜 S，S 战胜 P，P 战胜 H。两人使用相同魔法时为平局。

给出每轮中对手使用的魔法。你可以在第一轮任意选择一种魔法，之后每轮可以继续使用上一轮的魔法，也可以切换为另一种魔法。整个比赛中最多切换 $K$ 次。

求最多可以获胜多少轮。

输入格式

第一行包含两个整数 $N,K$。

接下来 $N$ 行，每行包含一个字符 H、S 或 P，表示对手在一轮中使用的魔法。

输出格式

输出一个整数，表示最多获胜轮数。

8 1
S
S
H
S
S
H
P
P

6

数据范围与提示

• 测试点 $1$ 满足 $1 \le N \le 10$，$K=1$
• 测试点 $2$ 满足 $1 \le N \le 30$，$K=0$
• 测试点 $3$ 至 $4$ 满足 $1 \le N \le 2500$，$1 \le K \le 6$
• 对于全部数据，$1 \le N \le 100000$，$0 \le K \le 20$