AT_joi2020ho_b JJOOII 2 (JJOOII 2)

[problemUrl]: https://atcoder.jp/contests/joi2020ho/tasks/joi2020ho_b ビ太郎は友人のビバ子から誕生日プレゼントに `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 $ を出力せよ． - - - - - -

入力は以下の形式で標準入力から与えられる．$ N,\ K $ は整数である．$ S $ は文字列である． > $ N $ $ K $ $ S $

文字列 $ S $ をレベル $ K $ の JOI 文字列に変換するのに必要な操作 $ 3 $ の回数の最小値を $ 1 $ 行で出力せよ．ただし，どのように操作を行っても文字列 $ 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 $ 点) 追加の制約はない. - - - - - - ### Sample Explanation 1 次のように操作を行うことで，文字列 $ S $ をレベル $ K $ のJOI文字列に変換できる． 1. まず操作 $ 1 $ を行う．文字列 $ S $ は `JIJOIOIIJ` になる． 2. 次に操作 $ 2 $ を行う．文字列 $ S $ は `JIJOIOII` になる． 3. 次に操作 $ 3 $ を行い，先頭から $ 2 $ 文字目を消す．文字列 $ S $ は `JJOIOII` になる． 4. 最後に操作 $ 3 $ を行い，先頭から $ 4 $ 文字目を消す．文字列 $ S $ は `JJOOII` になる． $ 2 $ 回未満の操作 $ 3 $ で変換することは不可能なので，$ 2 $ を出力する． - - - - - - ### Sample Explanation 2 操作を行わなくてもよい． - - - - - - ### Sample Explanation 3 この入力例では，どのように操作を行っても文字列 $ S $ をレベル $ 1 $ の JOI 文字列に変換できない．