学校文化节的展廊是一条直线，从左到右排着 n 个展位，每个展位由航模社或棋艺社中的一个社团布置。

组委会要把展廊划分成若干个连续的片区，使得每个片区至少包含 1 个展位、至多包含 k 个展位，并且每个展位恰好属于一个片区。划分完成后，每个片区的公共装饰由该片区内展位数较多的社团负责；如果两个社团的展位数相同，则约定由棋艺社负责。

今年的划分方案由航模社制定。为了扩大自己社团的影响力，航模社希望"由棋艺社负责"（即片区内棋艺社展位数不少于航模社展位数）的片区数量尽可能少。

棋艺社的同学想提前知道最坏的情况：在所有合法的划分方案中，"由棋艺社负责"的片区数量最少可能是多少？请你帮他们算出这个值。

输入的第一行是用空格隔开的两个整数，分别代表展位的个数 n 和每个片区包含展位数的上限 k。

输入的第二行是一个长度为 n 的字符串 s，s 中只含字符 H 和 G。若 s 的第 i 个字符是 H，则代表第 i 个展位由航模社布置，否则由棋艺社布置。

输出一行一个整数，代表"由棋艺社负责"的片区的最小可能数量。

样例说明

样例 1：k=1 时每个展位自成一个片区，棋艺社布置的 3 个展位对应的片区都由棋艺社负责，答案为 3。

样例 2：一种最优的划分方式是 [1,3],\ [4,5],\ [6,8]，即 GHH、GG、HGH 三个片区。第一、三个片区中航模社展位较多；只有第二个片区（两个展位都是棋艺社）由棋艺社负责，因此答案为 1。

样例 3：一种最优的划分方式是 [1,1],\ [2,6],\ [7,11],\ [12,16],\ [17,20]，即 H、HGGGG、GHHHG、HGGHH、GGGH 五个片区，其中只有第二、五个片区由棋艺社负责，答案为 2。注意本组数据中棋艺社展位总数（11 个）多于航模社（9 个），但通过精心划分，仍能把"棋艺社负责"的片区压到 2 个——把连续的 G 集中"打包"进少数片区、让 H 在其余片区中形成多数，是本题的关键直觉。此外，片区长度不必取满 k（如第一个片区只有 1 个展位）。

数据范围与提示

对于 100\% 的数据，保证 1 \leq k \leq n \leq 3 \times 10^5，s 的长度为 n，且只含字符 H 和 G。

本题共 20 个测试点，每个测试点 5 分。具体数据范围如下：

特殊性质 A：k=1。

特殊性质 B：k=n。

月赛26年7月动态规划单调队列