你可能玩过“石头,剪刀,布”,这个游戏在奶牛中同样流行,不过它的名字变成了“蹄子,剪刀,布”。
“蹄子,剪刀,布”和“石头,剪刀,布”的规则十分类似,两只奶牛数到三,然后出一个代表蹄子,剪刀或布的手势。蹄子胜过剪刀,剪刀胜过布,布胜过蹄子。特别地,如果两只奶牛的手势相同,则视为平局。
现在 FJ 和 Bassie 要进行 N 轮对抗。Bassie 已经预测了 FJ 每一轮要出的手势。然而 Bassie 很懒,她最多只想变换 K 次手势。
现在请你帮 Bassie 求出她最多能赢多少轮。
第一行输入两个整数 N,K(1≤N≤105,0≤K≤20)。
接下来 N 行,每行一个字母,代表 FJ 这一轮出的手势。H 代表蹄子(Hoof),S 代表剪刀(Scissors),P 代表布(Paper)。
5 1
P
P
H
P
S
4