Бовинополис состоит из ряда из \(N\) пастбищ (\(1 \leq N \leq 3 \cdot 10^5\)),
Каждое из которых содержит одну корову типа Holstein или Guernsey.
Правительство Бовинополиса хочет разделить его на некоторое количество
непрерывных районов так, чтобы каждый район содержал не более \(K\)
пастбищ (\(1 \leq K \leq N\)), и каждое пастбище содержится ровно в одном районе.
Поскольку сейчас правительство контролируется Holstein-ами, они хотят
найти такой способ разделения на районы, который минимизирует количество
районов, в которых коров Guernsey будет больше, чем коров Holstein или
столько же сколько Holstein.
Оппозиционная коалиция Guernsey старается выяснить вред от такого
переадминистрирования. Помогите им вычислить минимальное количество
районов, в которых у Guernsey будет большинство или равенство.
ФОРМАТ ВВОДА (файл redistricting.in):
Первая строка ввода содержит два разделённых пробелом целых числа \(N\) и \(K\).
Вторая строка содержит строку символов длиной \(N\). Каждый символ 'H' или 'G',
означающих Holstein или Guernsey, соответственно.
ФОРМАТ ВЫВОДА (файл redistricting.out):
Выведите минимально возможное количество районов, в которых у Guernsey
будет большинство или равенство.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 2
HGHGGHG
|
3
|