题目描述

定义有连续 $K$ 个 $\tt J$ 和连续 $K$ 个 $\tt O$ 和连续 $K$ 个 $\tt I$ 组成的字符串为 $K$ 阶 JOI 串。

比如，$\tt JJOOII$ 为 $2$ 阶 JOI 串，但是，注意要有顺序，比如 $\tt OOJJII$ 就不是 $2$ 阶 JOI 串。

现在，给定一个长度为 $N$ 的字符串 $S$，可以对他进行 $3$ 种操作：

• 操作 $1$：删除 $S$ 开头的字符
• 操作 $2$：删除 $S$ 结尾的字符
• 操作 $3$：删除 $S$ 除了开头和结尾之外的一个字符

我们要通过这些操作让 $S$ 变为 $K$ 阶 JOI 串。

但是，我们想让操作 $3$ 尽量的少。

所以我们想知道，变为 $K$ 阶 JOI 串操作 $3$ 最少需要进行多少次？

如果不能变为 $K$ 阶 JOI 串，那么输出 $-1$。

输入格式

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

输出格式

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

10 2
OJIJOIOIIJ

2

9 3
JJJOOOIII

0

9 1
IIIOOOJJJ

-1

提示

样例 1 解释

1. 进行一次操作 $1$，变为 $\tt JIJOIOIIJ$。
2. 进行一次操作 $2$，变为 $\tt JIJOIOII$。
3. 进行一次操作 $3$，删掉字符 $2$，变为 $\tt JJOIOII$。
4. 进行一次操作 $3$，删掉字符 $4$，变为 $\tt JJOOII$。

样例 2 解释

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

样例 3 解释

$\tt IIIOOOJJJ$ 无法变为 $1$ 阶 JOI 串，无解。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（1 pts）：$N \le 21$。
• Subtask 2（12 pts）：$N \le 3000$。
• Subtask 3（87 pts）：无特殊限制。

对于 $100\%$ 的数据：

• $3 \le N \le 2 \times 10^5$。
• $1 \le K \le \dfrac{N}{3}$。
• $S$ 只包含 $\tt J$，$\tt O$，$\tt I$ 且长度为 $N$。

说明

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