题目描述

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

10 2
OJIJOIOIIJ

2

9 3
JJJOOOIII

0

9 1
IIIOOOJJJ

-1

数据范围与提示

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