B - JJOOII 2 (JJOOII 2) Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点: 100

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

K1 以上の整数とする.K 個の文字 JK 個の文字 OK 個の文字 I をこの順に並べた文字列をレベル K の JOI 文字列と呼ぶことにする.例えば,JJOOII はレベル 2 の JOI 文字列である.

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

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

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

長さ N の文字列 S1 以上の整数 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}
  • SJ, O, I3 種類の文字からなる長さ 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 を行う.文字列 SJIJOIOIIJ になる.
  2. 次に操作 2 を行う.文字列 SJIJOIOII になる.
  3. 次に操作 3 を行い,先頭から 2 文字目を消す.文字列 SJJOIOII になる.
  4. 最後に操作 3 を行い,先頭から 4 文字目を消す.文字列 SJJOOII になる.

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


入力例 2

9 3
JJJOOOIII

出力例 2

0

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


入力例 3

9 1
IIIOOOJJJ

出力例 3

-1

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


Source Name

JOI 2019/2020 本選 問題2