003 - JOIJOI(JOIJOI)

問題

ビ太郎は友人のビバ子から誕生日プレゼントに$J,O,I$の3種類の文字からなる長さ$N$の文字列$S$をもらった。
ビ太郎はJOIという文字列が好きなので、文字列$S$に$K$個以上の部分文字列JOIが含まれるようにしたい。
部分文字列について、例えば、JOIIOJOIIは"JOI"IO"JOI"Iのように部分文字列JOIを2つ含んでいる。
ビ太郎は、文字列$S$に以下の操作を任意の回数行うことで、部分文字列JOIを$K$個以上含むようにすることにした。

操作:文字列$S$中の任意の1文字を選び、その文字を任意の1文字へと置き換える。

操作を行うのは面倒なので、操作を行う回数をできるだけ少なくして、文字列$S$に部分文字列JOIが$K$個以上含まれるようにしたい。
長さ$N$の文字列$S$と整数$K$が与えられたとき、文字列$S$に部分文字列JOIが$K$個以上含まれるようにするのに必要な操作の回数の最小値を出力するプログラムを作成せよ。

制約

• $3 \leq N \leq 3000$
• $1 \leq K \leq N/3$
• $S$は長さ$N$の文字列である。
• $S$の各文字は$J,O,I$のいずれかである。
• $N,K$は整数である。

小課題

• 1.(3点)$N=3,K=1$
• 2.(11点)$K=1$
• 3.(11点)$N=3K$
• 4.(48点)$N \leq 10$
• 5.(27点)追加の制約はない。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$
$S$

出力

文字列$S$に部分文字列JOIが$K$個以上含まれるようにするのに必要な操作の回数の最小値を出力せよ。 出力の最後に改行を入れること。

入出力例

入力例1

7 2
JOJOIOI

出力例1

2

3文字目をI、5文字目をJに置き換えることで、文字列$S$はJOIOJOIとなり、これは部分文字列JOIを2個含んでいる。
2回未満の操作で部分文字列JOIを2個以上含むようにすることは不可能なので、2を出力する。
この入力例は小課題$1,4,5$の制約を満たす。

入力例2

3 1
OIJ

出力例2

3

この入力例はすべての小課題の制約を満たす。

入力例3

12 4
JOIOJOOIOJJO

出力例3

8

この入力例は小課題$3,5$の制約を満たす。

入力例4

11 1
OOIOIJJIOIO

出力例4

1

この入力例は小課題$2,5$の制約を満たす。