题目描述

译自 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

input

10 2
OJIJOIOIIJ

output

2

你可以通过按以下顺序执行操作来将 $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

input

9 3
JJJOOOIII

output

0

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

样例 3

input

9 1
IIIOOOJJJ

output

-1

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

数据范围与提示

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