#3253. 「JOI 2020 Final」JJOOII 2

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: alpha1022

题目描述

译自 JOI 2020 Final T2「JJOOII 2 / JJOOII 2

比太郎收到了一个长度为 N 的字符串 S 作为他的生日礼物,且这个字符串仅由 \texttt J,\texttt O,\texttt I 组成。

对于所有正整数 K ,若一个字符串仅由 K 个连续的 \texttt J K 个连续的 \texttt O K 个连续的 \texttt I 顺次连接而成,则我们称这个字符串为 K 级 JOI-串
例如, \texttt{JJOOII} 就是一个 2 级 JOI-串。

比太郎热衷于构造 K 级 JOI-串,于是他打算通过以任意顺序使用以下三个操作任意次来将字符串 S 构造为一个 K 级 JOI-串:

  1. 删除 S 的开头字符。
  2. 删除 S 的结尾字符。
  3. 删除 S 的一个非开头且非结尾的字符。

由于操作 3 十分耗时,比太郎想要尽可能少地使用操作 3
请对于给定的长度为 N 的字符串 S 和一个正整数 K ,输出将其构造为 K 级 JOI-串所需要的最少的操作 3 的次数。
若无解,请输出 -1

输入格式

第一行,两个正整数 N,K
第二行,一个字符串 S

输出格式

一行,一个整数,表示操作 3 的最少次数或 -1

样例

样例输入 1

10 2
OJIJOIOIIJ

样例输出 1

2

样例解释 1

你可以通过按以下顺序执行操作来将 S 构造为一个 K 级 JOI-串:

  1. 使用操作 1 S 变为 \texttt{JIJOIOIIJ}
  2. 使用操作 2 S 变为 \texttt{JIJOIOII}
  3. 使用操作 3 删除第 2 个字符, S 变为 \texttt{JJOIOII}
  4. 使用操作 3 删除第 4 个字符, S 变为 \texttt{JJOOII}

可以证明没有更优解,故输出 2

样例输入 2

9 3
JJJOOOIII

样例输出 2

0

样例解释 2

显然,在这个样例中你甚至不需要任何操作。

样例输入 3

9 1
IIIOOOJJJ

样例输出 3

-1

样例解释 3

显然,在这个样例中你的一切操作都是无用功。

数据范围与提示

对于所有测试数据, 3 \le N \le 2 \times 10^5, 1 \le K \le \frac N3, S 是一个仅有 \texttt J, \texttt O, \texttt I 组成的字符串。

子任务编号 分值 N
1 1 N \le 21
2 12 N \le 3000
3 87