比太郎收到了朋友比巴子送的生日礼物，是一个由 $J$、$O$、$I$ 这 $3$ 种字符组成的长度为 $N$ 的字符串 $S$。

设 $K$ 为大于等于 $1$ 的整数。将 $K$ 个字符 $J$、$K$ 个字符 $O$、$K$ 个字符 $I$ 按此顺序排列而成的字符串，称为等级为 $K$ 的 JOI 字符串。例如，JJOOII 是等级为 $2$ 的 JOI 字符串。

比太郎很喜欢等级为 $K$ 的 JOI 字符串，因此他想通过任意次数、任意顺序地进行以下 $3$ 种操作，将字符串 $S$ 变换为等级为 $K$ 的 JOI 字符串。

• 操作 $1$：删除字符串 $S$ 的首字母。
• 操作 $2$：删除字符串 $S$ 的末尾字母。
• 操作 $3$：删除字符串 $S$ 中既不是首字母也不是末尾字母的某个字符。

由于操作 $3$ 很麻烦，比太郎希望在将字符串 $S$ 变换为等级为 $K$ 的 JOI 字符串的过程中，尽量减少操作 $3$ 的次数。

给定长度为 $N$ 的字符串 $S$ 和大于等于 $1$ 的整数 $K$，请编写程序输出将字符串 $S$ 变换为等级为 $K$ 的 JOI 字符串所需的最小操作 $3$ 的次数。如果无论如何都无法将字符串 $S$ 变换为等级为 $K$ 的 JOI 字符串，则输出 $-1$。

输入以如下格式从标准输入读入。$N,\ K$ 为整数，$S$ 为字符串。

$N$ $K$ $S$

请输出将字符串 $S$ 变换为等级为 $K$ 的 JOI 字符串所需的最小操作 $3$ 的次数。如果无论如何都无法变换，则输出 $-1$。

限制条件

• $3 \leq N \leq 200\,000$。
• $1 \leq K \leq \frac{N}{3}$。
• $S$ 是由 $J$、$O$、$I$ 这 $3$ 种字符组成的长度为 $N$ 的字符串。

子任务

1. ($1$ 分) $N \leq 21$。
2. ($12$ 分) $N \leq 3\,000$。
3. ($87$ 分) 无额外限制。

样例说明 1

可以按如下方式操作，将字符串 $S$ 变换为等级为 $K$ 的 JOI 字符串。

1. 首先进行操作 $1$，字符串 $S$ 变为 JIJOIOIIJ。
2. 接着进行操作 $2$，字符串 $S$ 变为 JIJOIOII。
3. 然后进行操作 $3$，删除从头数第 $2$ 个字符，字符串 $S$ 变为 JJOIOII。
4. 最后再进行一次操作 $3$，删除从头数第 $4$ 个字符，字符串 $S$ 变为 JJOOII。

无法通过少于 $2$ 次操作 $3$ 完成变换，因此输出 $2$。

样例说明 2

无需进行任何操作即可完成变换。

样例说明 3

对于此输入，无论如何操作都无法将字符串 $S$ 变换为等级为 $1$ 的 JOI 字符串。

由 ChatGPT 4.1 翻译