Ifri recibió una string ~S~ de longitud ~N~ de parte de Torvic como regalo de cumpleaños. La string ~S~ consta de tres tipos de caracteres, J, O e I. Para cada número entero positivo ~K~, llamaremos a la string que consta de ~K~ Js, ~K~ Os y ~K~ Is en este orden "String ~JOI~ de nivel ~K~". Por ejemplo, ~JJOOII~ es una string ~JOI~ de nivel 2.

A Ifri le gusta una string ~JOI~ de nivel ~K~, así que quiere hacer una a partir de la string ~S~ usando las siguientes tres operaciones cualquier número de veces en orden arbitrario:

• Operación ~1~: Ifri borra el primer caracter de ~S~.

• Operación ~2~: Ifri borra el último caracter de ~S~.

• Operación ~3~: Ifri borra un caracter de ~S~ que no es ni el primero ni el último.

Como la Operación ~3~ lleva mucho tiempo, Ifri quiere hacer una String ~JOI~ de nivel ~K~ con el menor número de Operaciones ~3~ posible. Es por eso que te pide a ti, su mejor amigo programador, que escribas un programa que dada una string ~S~ de longitud ~N~ y un entero positivo ~K~, imprima el menor número de Operaciones ~3~ necesarias para hacer una String ~JOI~ de nivel ~K~ a partir de ~S~ .

Si es imposible hacer una String ~JOI~ de nivel ~K~ con las operaciones dadas, imprime ~-1~ en su lugar.

Subtareas

1. (10 puntos) ~(N \leq 21)~.

2. (30 puntos) ~(N \leq 3 000)~.

3. (60 puntos) Sin restricciones adicionales.

Entrada

La primera línea de la entrada contiene dos enteros: ~N~ ~(3 \leq N \leq 2*10^5 )~ y ~K~ ~(1 \leq K \leq \frac{N}{3})~.

La segunda línea contiene la string ~S~, la cual consiste solo de letras J, O e I.

Salida

La salida debe contener el menor número de Operaciones ~3~ requeridas para hacer una String ~JOI~ de nivel ~K~ a partir de ~S~.

Si es imposible, imprime ~-1~.

Ejemplo de Entrada 1

10 2
OJIJOIOIIJ

Ejemplo de Salida 1

2

Puedes hacer una String ~JOI~ de nivel ~K~ a partir de la string ~S~ mediante las siguientes operaciones:

1. Utilizas la Operación ~1~ y ~S~ se convierte en ~JIJOIOIIJ~.
2. Utilizas la Operación ~2~ y ~S~ se convierte en ~JIJOIOII~.
3. Utilizas la Operación ~3~ para eliminar el segundo carácter y ~S~ se convierte en ~JJOIOII~.
4. Utilizas la Operación ~3~ para eliminar el cuarto carácter y ~S~ se convierte en ~JJOOII~.

Es imposible hacer una String ~JOI~ de nivel ~K~ con el uso de la Operación 3 menos de dos veces, por lo que debes imprimir 2.

Ejemplo de Entrada 2

9 3
JJJOOOIII

Ejemplo de Salida 2

0

No necesitas usar ninguna operación.

Ejemplo de Entrada 3

9 1
IIIOOOJJJ

Ejemplo de Salida 3

-1

Es imposible hacer una String ~JOI~ de nivel ~1~ a partir de ~S~.