ビ太郎は友人のビバ子から誕生日プレゼントに J，O，I の 3 種類の文字からなる長さ N の文字列 S をもらった．

K を 1 以上の整数とする．K 個の文字 J，K 個の文字 O，K 個の文字 I をこの順に並べた文字列をレベル K の JOI 文字列と呼ぶことにする．例えば，JJOOII はレベル 2 の JOI 文字列である．

ビ太郎はレベル K の JOI 文字列が好きなので，以下の 3 種類の操作を任意の回数，任意の順番で行うことで，文字列 S をレベル K の JOI 文字列に変換することにした．

• 操作 1   文字列 S の先頭の文字を消す．
• 操作 2   文字列 S の末尾の文字を消す．
• 操作 3   文字列 S の先頭でも末尾でもない文字を消す．

操作 3 を行うのは面倒なので，操作 3 を行う回数をできるだけ少なくして，文字列 S をレベル K の JOI 文字列に変換したい．

長さ N の文字列 S と 1 以上の整数 K が与えられたとき，文字列 S をレベル K の JOI 文字列に変換するのに必要な操作 3 の回数の最小値を出力するプログラムを作成せよ．ただし，どのように操作を行っても文字列 S をレベル K の JOI 文字列に変換できない場合は，代わりに −1 を出力せよ．

制約

• 3 \leqq N \leqq 200\,000．
• 1 \leqq K \leqq \frac{N}{3}．
• S は J，O，I の 3 種類の文字からなる長さ N の文字列である．

小課題

1. (1 点) N \leqq 21.
2. (12 点) N \leqq 3\,000.
3. (87 点) 追加の制約はない.

入力例 1

10 2
OJIJOIOIIJ

出力例 1

2

次のように操作を行うことで，文字列 S をレベル K のJOI文字列に変換できる．

1. まず操作 1 を行う．文字列 S は JIJOIOIIJ になる．
2. 次に操作 2 を行う．文字列 S は JIJOIOII になる．
3. 次に操作 3 を行い，先頭から 2 文字目を消す．文字列 S は JJOIOII になる．
4. 最後に操作 3 を行い，先頭から 4 文字目を消す．文字列 S は JJOOII になる．

2 回未満の操作 3 で変換することは不可能なので，2 を出力する．

入力例 2

9 3
JJJOOOIII

出力例 2

0

操作を行わなくてもよい．

入力例 3

9 1
IIIOOOJJJ

出力例 3

-1

この入力例では，どのように操作を行っても文字列 S をレベル 1 の JOI 文字列に変換できない．