Description

A string made up of $K$ consecutive $\tt J$, followed by $K$ consecutive $\tt O$, followed by $K$ consecutive $\tt I$ is called a $K$-th order JOI string.

For example, $\tt JJOOII$ is a $2$-th order JOI string. However, note that the order matters. For example, $\tt OOJJII$ is not a $2$-th order JOI string.

Now, given a string $S$ of length $N$, you may perform the following three operations:

• Operation 1: Delete the first character of $S$.
• Operation 2: Delete the last character of $S$.
• Operation 3: Delete one character of $S$ other than the first and the last.

We want to make $S$ become a $K$-th order JOI string using these operations.

However, we want to use Operation 3 as few times as possible.

So, what is the minimum number of times Operation 3 must be performed to make $S$ into a $K$-th order JOI string?

If it is impossible to make it into a $K$-th order JOI string, output $-1$.

Input Format

The first line contains two integers $N, K$, representing the string length and the order $K$ of the JOI string to construct.
The second line contains $N$ characters, representing the string $S$.

Output Format

Output one integer: the minimum number of times Operation 3 needs to be performed.
If it is impossible to make it into a $K$-th order JOI string, output $-1$.

10 2
OJIJOIOIIJ

2

9 3
JJJOOOIII

0

9 1
IIIOOOJJJ

-1

Hint

Explanation for Sample 1

1. Perform Operation 1 once to get $\tt JIJOIOIIJ$.
2. Perform Operation 2 once to get $\tt JIJOIOII$.
3. Perform Operation 3 once: delete character $2$ to get $\tt JJOIOII$.
4. Perform Operation 3 once: delete character $4$ to get $\tt JJOOII$.

Explanation for Sample 2

$\tt JJJOOOIII$ is already a $3$-th order JOI string, so no operations are needed.

Explanation for Sample 3

$\tt IIIOOOJJJ$ cannot be turned into a $1$-st order JOI string, so there is no solution.

Constraints

This problem uses bundled testdata.

• Subtask 1 (1 pts): $N \le 21$.
• Subtask 2 (12 pts): $N \le 3000$.
• Subtask 3 (87 pts): No additional constraints.

For $100\%$ of the testdata:

• $3 \le N \le 2 \times 10^5$.
• $1 \le K \le \dfrac{N}{3}$.
• $S$ contains only $\tt J$, $\tt O$, $\tt I$, and has length $N$.

Note

Translated from The 19th Japanese Olympiad in Informatics Final Round B JJOOII 2。

Translated by ChatGPT 5