Задача динамического программирования

Кто-нибудь может помочь мне найти оптимальный алгоритм динамического программирования для этой проблемы

Уже в пути к обеду участники CCC выстраиваются в очередь за своим восхитительным кудрявым картофелем фри. N (1 ≤ N ≤ 100) участников выстроились в очередь, чтобы войти в кафетерий.

Доктор V, который руководит CCC, понял в В последнюю минуту программисты просто ненавидят стоять в очереди рядом с программистами, которые используют другой язык. К счастью, в CCC разрешены только два языка: Gnold и Helpfile. Более того, участники решили, что они войдут в кафетерий, только если они будут в группе из не менее K (1 ≤ K ≤ 6) участников.

Доктор V решил повторить следующую схему:

* He will find a group of K or more competitors who use the same language standing next to each other in line and send them to dinner.
* The remaining competitors will close the gap, potentially putting similar-language competitors together.

Итак, доктор V записал для вас последовательность конкурентов. Могут ли все участники пообедать? Если да, то какое минимальное количество групп участников нужно отправить на обед? Входные данные

В первой строке записаны два целых числа N и K. Вторая строка содержит N символов, которые представляют собой последовательность участников в строке (H представляет файл справки, G представляет Gnold). Выходные данные

Выведите в одной строке единственное число, которое представляет собой минимальное количество групп, формируемых на обед. Если не все программисты могут обедать, выведите -1. ​​