#P6878. [JOI 2020 Final] JJOOII 2

[JOI 2020 Final] JJOOII 2

题目描述

定义有连续 KKJ\tt J 和连续 KKO\tt O 和连续 KKI\tt I 组成的字符串为 KK 阶 JOI 串。

比如,JJOOII\tt JJOOII22 阶 JOI 串,但是,注意要有顺序,比如 OOJJII\tt OOJJII 就不是 22 阶 JOI 串。

现在,给定一个长度为 NN 的字符串 SS,可以对他进行 33 种操作:

  • 操作 11:删除 SS 开头的字符
  • 操作 22:删除 SS 结尾的字符
  • 操作 33:删除 SS 除了开头和结尾之外的一个字符

我们要通过这些操作让 SS 变为 KK 阶 JOI 串。

但是,我们想让操作 33 尽量的少。

所以我们想知道,变为 KK 阶 JOI 串操作 33 最少需要进行多少次?

如果不能变为 KK 阶 JOI 串,那么输出 1-1

输入格式

第一行两个整数 N,KN,K 代表字符串长度和要构造的 JOI 串的阶数。
第二行 NN 个字符代表字符串 SS

输出格式

一行一个整数代表操作 33 的最小进行次数。
如果不能变为 KK 阶 JOI 串,那么输出 1-1

10 2
OJIJOIOIIJ
2
9 3
JJJOOOIII
0
9 1
IIIOOOJJJ
-1

提示

样例 1 解释

  1. 进行一次操作 11,变为 JIJOIOIIJ\tt JIJOIOIIJ
  2. 进行一次操作 22,变为 JIJOIOII\tt JIJOIOII
  3. 进行一次操作 33,删掉字符 22,变为 JJOIOII\tt JJOIOII
  4. 进行一次操作 33,删掉字符 44,变为 JJOOII\tt JJOOII

样例 2 解释

JJJOOOIII\tt JJJOOOIII 已经是 33 阶 JOI 串了,所以不需要进行操作。

样例 3 解释

IIIOOOJJJ\tt IIIOOOJJJ 无法变为 11 阶 JOI 串,无解。

数据规模与约定

本题采用捆绑测试。

  • Subtask 1(1 pts):N21N \le 21
  • Subtask 2(12 pts):N3000N \le 3000
  • Subtask 3(87 pts):无特殊限制。

对于 100%100\% 的数据:

  • 3N2×1053 \le N \le 2 \times 10^5
  • 1KN31 \le K \le \dfrac{N}{3}
  • SS 只包含 J\tt JO\tt OI\tt I 且长度为 NN

说明

翻译自 第19回日本情報オリンピック 本選 B JJOOII 2