¿Puede alguien ayudarme a encontrar un algoritmo de programación dinámica óptimo paraeste problem

n el camino a la cena, los competidores de CCC hacen cola para sus deliciosas papas rizadas. Los competidores N (1 ≤ N ≤ 100) se han alineado con una sola fila para ingresar a la cafetería.

Doctor V, que dirige el CCC, se dio cuenta en el último minuto de que los programadores simplemente odian estar en la fila junto a los programadores que usan un lenguaje diferente. Afortunadamente, solo se permiten dos idiomas en el CCC: Gnold y Helpfile. Además, los competidores han decidido que solo ingresarán a la cafetería si están en un grupo de al menos K (1 ≤ K ≤ 6) competidores.

Doctor V decidió repetir el siguiente esquema:

* 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.

So Doctor V grabó la secuencia de competidores para ti. ¿Pueden cenar todos los competidores? Si es así, ¿cuál es el número mínimo de grupos de competidores que se enviarán a cenar? Entrad

La primera línea contiene dos enteros N y K. La segunda línea contiene N caracteres que son la secuencia de los competidores en línea (H representa el archivo de ayuda, G representa Gnold) Salida

Salida, en una línea, el número único que es el número mínimo de grupos que se forman para la cena. Si no todos los programadores pueden cenar, salida -1.