시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 109 | 77 | 70 | 70.707% |
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:
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.
J
, O
and I
.번호 | 배점 | 제한 |
---|---|---|
1 | 1 | N ≤ 21. |
2 | 12 | N ≤ 3 000. |
3 | 87 | No additional constraints. |
10 2 OJIJOIOIIJ
2
You can make a JOI-string of level K from string S by the following operations:
JIJOIOIIJ
.JIJOIOII
.JJOIOII
.JJOOII
.It is impossible to make a JOI-string of level K with using Operation 3 less than twice, so you should print 2.
9 3 JJJOOOIII
0
You need not use an operation.
9 1 IIIOOOJJJ
-1
In this sample, it is impossible to make a JOI-string of level 1 from string S .