AT_joi2020ho_b JJOOII 2 (JJOOII 2)

比太郎收到了朋友比巴子送的生日礼物，是一个由 $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 翻译