题目背景

USACO 19年一月月赛铂金组第一题

题目描述

奶牛们的特大城市，牛都，要进行重新分区了！——这总是一个在居住在这里的两大主要种族（荷斯坦牛和更赛牛）之间富有争议的政治事件，因为两大种族都想要在牛都政府中保持足够的影响力。

牛都的大都市圈由一列 $n$ 块牧草地组成，每块里有一头奶牛，均为荷斯坦牛 (Holstein) 和更赛牛 (Guernsey) 之一。

牛都政府想要将大都市圈划分为若干个连续的区，使得每个区至少包含一块牧草地且至多包含 $k$ 块牧草地，并且每块牧草地恰好属于一个区。由于政府当前由荷斯坦牛控制，她们想要找到一种分区方式能够最小化更赛牛较多或者均势的区的数量（如果更赛牛的数量与荷斯坦牛的数量相等那么这个区就是均势的）。

有一个关心政治的更赛牛团体想要知道政府的分区计划可能会对她们造成多少损害。帮助她们求出最坏情况，也就是更赛牛较多或是均势的区的最小可能的数量。

输入格式

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

输入的第二行是一个长度为 $n$ 的字符串 $s$，$s$ 中只含字符 H 和 G。若 $s$ 的第 $i$ 个字符是 H，则代表第 $i$ 块草地上的奶牛是荷斯坦牛，否则是更赛牛。

输出格式

输出一行一个整数，代表更赛牛较多或者优势区的最小可能数量。

7 2
HGHGGHG

3

提示

样例解释

一种可能的划分方式是 $[1],~[2, 3],~[4, 5],~[6, 7]$。第二、四个区是均势的区，第三个区是更赛牛优势的区。

数据范围

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