题目描述

您可能听说过"石头剪刀布"游戏。奶牛喜欢玩他们称之为"蹄、纸、剪刀"的类似游戏。 "蹄、纸、剪刀"的规则很简单。两只母牛互相对 抗。

他们都数到三，然后每个人同时做出一个手势，代表一只蹄子、一张纸或一把剪刀。蹄能打剪刀（因为蹄子能砸剪刀），剪刀能打纸（因为剪刀能剪纸），纸能打蹄（因为蹄子能剪纸）。

例如，如果第一头奶牛做出"蹄子"手势，第二头奶牛做出"纸"手势，则第二头奶牛获胜。当然，如果两头奶牛做出相同的手势，也可以打领带。

$\red{Farmer John }$想在"蹄、纸、剪刀"的 $\red{NN }$场比赛$\red{（1≤}$$\red{N≤}$$\red{100,000）}$中与他的奖品奶牛 $\red{Bessie }$比赛。

$\red{Bessie }$是游戏专家，可以在 $\red{FJ }$做出每个手势之前预测他的每一个手势。不幸的是，身为牛的贝西也很懒惰.结果，她倾向于连续多次播放相同的手势。

事实上，她在整组游戏中最多只愿意切换手势$\red{K}$次$\red{（0≤}$$\red{K≤}$$\red{20）}$。例如，如果$\red{K=2，}$她可能会在前几场比赛中玩"蹄"，然后切换到"纸"一段时间，然后玩"蹄"完成剩余的游戏。

鉴于 $\red{FJ }$将要玩的手势顺序，请确定 $\red{Bessie }$可以赢得的最大游戏数。

输入格式

输入文件的第一行包含$\red{N}$和$\red{K}$。

其余的$\red{N}$行包含$\red{FJ}$的手势，每个手势可以是$\red{H}$、$\red{P}$或$\red{S}$。

输出格式

打印贝西最多可以赢的游戏数，因为她最多只能改变$\red{K}$次手势。

样例

输入样例

5 1
P
P
H
P
S

输出样例

4