Изменение границ
Коровий мегаполис Бовинополис меняет районы! - всегда спорный политический процесс между двумя основными породами коров (голштинской и гернсейской), живущими там, поскольку обе породы хотят сохранить достаточное влияние в правительстве Бовинополиса.
Большая столичная область Бовинополис состоит из ряда n пастбищ, каждое из которых содержит одну корову, которая является либо голштинской, либо гернсианской.
Правительство Бовинополиса хочет разделить большую столичную область на некоторое количество прилегающих районов, чтобы каждый район содержал не более k пастбищ, а каждое пастбище находилось ровно в одном районе. Поскольку правительство в настоящее время контролируется голштинами, они хотят найти способ перераспределения, который сведет к минимуму количество районов с большинством у гернсейцев или равных районов (район считается равным, если количество гернсейцев равно количеству голштинцев).
Обеспокоенная коалиция гернсейцев пытается выяснить, какой ущерб может быть нанесен правительством перераспределением округов. Помогите им определить наихудшее минимальное количество районов, в которых либо будет большинство гернсейцев, либо равных районов.
Входные данные
Первая строка содержит два целых числа n (1 ≤ n ≤ 3 * 10^5) и k (1 ≤ k ≤ n). Вторая строка содержит строку длины n. Каждый символ - это 'H' или 'G' для голштинской или гернсианской коровы.
Выходные данные
Выведите минимальное возможное количество районов, в которых либо гернсианцы будут составлять большинство, либо районы будут равными.