奶牛大都市 Bovinopolis 正在进行选区划分！对于居住在那里的两个主要奶牛品种（荷斯坦牛 Holstein 和根西牛 Guernsey）来说，这总是一个充满争议的政治过程，因为两个品种都希望确保它们在 Bovinopolis 政府中保持足够的政治影响力。

Bovinopolis 的大都市区由一排 $N$ 个牧场组成（$1 \leq N \leq 3 \cdot 10^5$），每个牧场里有一头奶牛，品种要么是荷斯坦牛，要么是根西牛。

Bovinopolis 政府希望将大都市区划分为若干个连续的选区，使得每个选区最多包含 $K$ 个牧场（$1 \leq K \leq N$），并且每个牧场恰好属于一个选区。由于政府目前由荷斯坦牛控制，他们希望找到一种重新划分选区的方法，以最小化根西牛占多数或平局的选区数量（如果一个选区中根西牛的数量大于或等于荷斯坦牛的数量，则该选区被视为根西牛占多数或平局）。

一个由根西牛组成的关心此事的联盟正试图弄清楚政府的重新划分可能会造成多大的损害。请帮助他们计算出根西牛占多数或平局的选区数量的最小值（最坏情况下的最小值）。

输入格式

第一行包含两个由空格分隔的整数 $N$ 和 $K$。第二行包含一个长度为 $N$ 的字符串。每个字符要么是 'H'，要么是 'G'，分别代表荷斯坦牛或根西牛。

输出格式

请输出根西牛占多数或平局的选区数量的最小值。

样例

样例输入 1

7 2
HGHGGHG

样例输出 1

3