Problem Description

A string consisting of consecutive $K$ $\tt J$s, followed by consecutive $K$ $\tt O$s, and then followed by consecutive $K$ $\tt I$s is defined as a $K$-level JOI string.

For example, $\tt$ is a $2$-level JOI string. However, note that the order is important; for instance, $\tt$ is not a $2$-level JOI string.

Given a string $S$ of length $N$, you can perform three types of operations on it:

• Operation 1: Delete the first character of $S$.
• Operation 2: Delete the last character of $S$.
• Operation 3: Delete a character from $S$ that is neither the first nor the last.

We aim to transform $S$ into a $K$-level JOI string using these operations, with the goal of minimizing the number of Operation 3.

We need to determine the minimum number of Operation 3 required to achieve this transformation. If it is not possible to transform $S$ into a $K$-level JOI string, output $-1$.

Input Format

The first line contains two integers $N$ and $K$, representing the length of the string and the level of the JOI string to be constructed, respectively.
The second line contains $N$ characters representing the string $S$.

Output Format

Output a single integer representing the minimum number of Operation 3 required. If it is not possible to transform $S$ into a $K$-level JOI string, output $-1$.

Sample Input and Output

Sample Input #1

10 2
OJIJOIOIIJ

Sample Output #1

2

Sample Input #2

9 3
JJJOOOIII

Sample Output #2

0

Sample Input #3

9 1
IIIOOOJJJ

Sample Output #3

-1

Notes

Sample 1 Explanation

1. Perform Operation 1 once, resulting in $\tt$.
2. Perform Operation 2 once, resulting in $\tt$.
3. Perform Operation 3 once, deleting character 2, resulting in $\tt$.
4. Perform Operation 3 once, deleting character 4, resulting in $\tt$.

Sample 2 Explanation

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

Sample 3 Explanation

$\tt$ cannot be transformed into a $1$-level JOI string, hence no solution.

Data Constraints

This problem is bundled.

• 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 data:

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

Notes

Translated from the 19th Japanese Olympiad in Informatics Final Round B JJOOII 2.

见题面 Input 部分

见题面 Output 部分