题目描述

小A和小B正在进行一场魔法对决。他们学习了三种不同的魔法：火焰魔法、风暴魔法和水滴魔法，分别用字母 H、S 和 P 表示。

其中：

• 火焰魔法（H）强于风暴魔法（S）。
• 风暴魔法（S）强于水滴魔法（P）。
• 水滴魔法（P）强于火焰魔法（H）。

比赛共有 $N$ 轮，每轮两人各施展一种魔法。如果小A的施展的魔法强于小B的魔法，则小A赢得这一轮。如果两人施展的魔法相同，则本轮平局。否则，小A输掉该轮。

第一局比赛，小A可以施展任意的魔法，后续的每轮比赛，小A要么使用和上一轮比赛一样魔法，要么切换和上一轮比赛不同的魔法。由于小A对魔法的切换还不够熟练，他将在比赛中最多切换 $K$ 次魔法。

给出小B在比赛中每次使用的魔法数据，请编程计算出，$N$ 轮比赛结束后，小A最多能赢得多少轮比赛。

输入格式

第一行输入两个整数 $N$ 和 $K$，表示比赛轮数和小A可以切换的魔法次数。

接下来的 $N$ 行，每行一个字母，表示小B在每轮比赛中使用的魔法。

输出格式

输出一个整数，表示小A在最多切换 $K$ 次魔法的情况下，可以赢得的比赛轮数。

样例

输入

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 \sim 4$ 满足 $1 \le N \le 2500$，$1 \le K \le 6$。

测试点 $5 \sim 10$，满足 $1 \le N \le 100,000$，$0 \le K \le 20$。