Problem Description

Bitaro received a birthday present from his friend Bibako, which is a string \( S \) of length \( N \) consisting of three types of characters: J, O, and I.

Let \( K \) be an integer greater than or equal to 1. A string consisting of \( K \) characters J, followed by \( K \) characters O, followed by \( K \) characters I, is called a level \( K \) JOI string. For example, JJOOII is a level 2 JOI string.

Bitaro likes level \( K \) JOI strings, so he decided to convert the string \( S \) into a level \( K \) JOI string by performing the following operations any number of times in any order:

• Operation 1: Remove the first character of the string \( S \).
• Operation 2: Remove the last character of the string \( S \).
• Operation 3: Remove a character from the string \( S \) that is neither the first nor the last character.

Since performing Operation 3 is cumbersome, Bitaro wants to minimize the number of times Operation 3 is performed to convert the string \( S \) into a level \( K \) JOI string.

Given a string \( S \) of length \( N \) and an integer \( K \) greater than or equal to 1, create a program that outputs the minimum number of times Operation 3 is needed to convert the string \( S \) into a level \( K \) JOI string. If it is impossible to convert the string \( S \) into a level \( K \) JOI string by any means, output \( -1 \) instead.

Input Format

The input is given from the standard input in the following format. \( N \) and \( K \) are integers. \( S \) is a string.

\( N \) \( K \) \( S \)

Output Format

Output the minimum number of times Operation 3 is needed to convert the string \( S \) into a level \( K \) JOI string. If it is impossible to convert the string \( S \) into a level \( K \) JOI string by any means, output \( -1 \) instead.

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/Hints

Constraints

• \( 3 \leq N \leq 200,000 \).
• \( 1 \leq K \leq \frac{N}{3} \).
• \( S \) is a string of length \( N \) consisting of the characters J, O, and I.

Subtasks

1. (1 point) \( N \leq 21 \).
2. (12 points) \( N \leq 3,000 \).
3. (87 points) No additional constraints.

Sample Explanation 1

The string \( S \) can be converted into a level \( K \) JOI string by performing the following operations:
1. First, perform Operation 1. The string \( S \) becomes JIJOIOIIJ.
2. Next, perform Operation 2. The string \( S \) becomes JIJOIOII.
3. Then, perform Operation 3 to remove the second character from the beginning. The string \( S \) becomes JJOIOII.
4. Finally, perform Operation 3 to remove the fourth character from the beginning. The string \( S \) becomes JJOOII.
It is impossible to convert the string \( S \) with fewer than 2 operations of type 3, so output 2.

Sample Explanation 2

No operations are needed.

Sample Explanation 3

In this input example, it is impossible to convert the string \( S \) into a level 1 JOI string by any means.

见题面 Input 部分

见题面 Output 部分