JJOOII 2 (JJOOII 2)

ビ太郎は友人のビバ子から誕生日プレゼントに 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\) 点) 追加の制約はない.

JOI 2020 · JCIOI · CC BY-SA 4.0