小 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 次魔法的情况下，可以赢得的比赛轮数。

样例 1 说明

小 B 施展魔法顺序是：S S H S S H P P。

如果小 A 固定使用火焰魔法（H），只能赢得第 1、2 和第 4、5 轮比赛。

小 A 可以通过切换一次魔法，在第 7 轮切换为风暴魔法（S），从而赢得第 1、2、4、5 和第 7、8 轮比赛。

因此，在最多切换 1 次魔法的情况下，小 A 可以赢得 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 \leq N \leq 100,000，0 \leq K \leq 20 。

月赛动态规划2024