시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 14 11 9 81.818%

문제

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 .