시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 35 29 24 85.714%

## 문제

Bitaro received a string S of length N for his birthday present. String S consists of three kinds of characters, J, O and I.

For each positive integer K, we will call the string which consists of K J’s, K O’s, and K I’s in this order JOI-string of level K. For example, JJOOII is a JOI-string of level 2.

Bitaro likes a JOI-string of level K, so he is going to make a JOI-string of level K from string S by using the following three operations any number of times in arbitrary order:

• Operation 1 Bitaro deletes the first character of S.
• Operation 2 Bitaro deletes the last character of S.
• Operation 3 Bitaro deletes a character of S which is neither the first nor the last.

Because using Operation 3 is time-consuming, Bitaro wants to make a JOI-string of level K with as small number of Operation 3 as possible.

Write a program which, given a string S of length N and a positive integer K, prints the smallest number of Operation 3 required to make a JOI-string of level K from S . If it is impossible to make a JOI-string of level K with the operations, print −1 instead.

## 입력

Read the following data from the standard input. N and K are integers. S is a string.

N K
S

## 출력

Write one line to the standard output. The output should contain the smallest number of Operation 3 required to make a JOI-string of level K from S . If it is impossible to make a JOI-string of level K, print −1 instead.

## 제한

• 3 ≤ N ≤ 200 000.
• 1 ≤ K ≤ N/3.
• S is a string of length N which consists of J, O and I.

## 예제 입력 1

10 2
OJIJOIOIIJ


## 예제 출력 1

2


You can make a JOI-string of level K from string S by the following operations:

1. You use Operation 1 and S becomes JIJOIOIIJ.
2. You use Operation 2 and S becomes JIJOIOII.
3. You use Operation 3 to remove the second character and S becomes JJOIOII.
4. You use Operation 3 to remove the fourth character and S becomes JJOOII.

It is impossible to make a JOI-string of level K with using Operation 3 less than twice, so you should print 2.

## 예제 입력 2

9 3
JJJOOOIII


## 예제 출력 2

0


You need not use an operation.

## 예제 입력 3

9 1
IIIOOOJJJ


## 예제 출력 3

-1


In this sample, it is impossible to make a JOI-string of level 1 from string S .