문제
비타로는 생일 선물로 N 길이의 문자열 S를 받았습니다. 문자열 S는 J, O, I 세 종류의 문자로 구성됩니다.
각 양의 정수 K에 대해 KJ, KO, KI 순서로 구성된 문자열을 레벨 K의 JOI 문자열이라고 부릅니다. 예를 들어 JJOOII는 레벨 2의 JOI 문자열입니다.
Bitaro는 레벨 K의 JOI 문자열을 좋아하므로 다음 세 가지 작업을 임의의 순서로 여러 번 사용하여 문자열 S에서 레벨 K의 JOI 문자열을 만들 것입니다.
작전 1 비타로는 S의 첫 글자를 삭제한다.
작전 2 비타로는 S의 마지막 문자를 삭제한다.
작전 3 비타로는 처음도 마지막도 아닌 S의 문자를 삭제한다.
작업 3을 사용하는 것은 시간이 많이 걸리기 때문에 Bitaro는 가능한 적은 수의 작업 3을 사용하여 레벨 K의 JOI 문자열을 만들고 싶어합니다.
길이 N의 문자열 S와 양의 정수 K가 주어지면 S에서 레벨 K의 JOI 문자열을 만드는 데 필요한 연산 3의 가장 작은 숫자를 인쇄하는 프로그램을 작성하세요. 연산으로 레벨 K의 JOI 문자열을 만드는 것이 불가능하다면 대신 -1을 인쇄하세요.
입력
표준 입력에서 다음 데이터를 읽습니다. N과 K는 정수입니다. S는 문자열입니다.
N K
S
[제한]
3 ≤ N ≤ 200,000.
1 ≤ K ≤ N/3.
S는 J, O, I로 구성된 길이 N의 문자열입니다.
출력
표준 출력에 한 줄을 씁니다. 출력에는 S에서 레벨 K의 JOI 문자열을 만드는 데 필요한 최소 작업 3 수가 포함되어야 합니다. 레벨 K의 JOI 문자열을 만드는 것이 불가능하다면 대신 -1을 인쇄하세요.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 1점 | N ≤ 21 |
| #2 | 12점 | N ≤ 3 000 |
| #3 | 87점 | 추가 제한 없음 |
예제1
102
OJIJOIOIIJ
2
다음 작업을 통해 문자열 S에서 레벨 K의 JOI 문자열을 만들 수 있습니다.
Operation 1을 사용하면 S는 JIJOIOIIJ가 됩니다.
Operation 2를 사용하면 S는 JIJOIOII가 됩니다.
작업 3을 사용하여 두 번째 문자를 제거하면 S는 JJOIOII가 됩니다.
작업 3을 사용하여 네 번째 문자를 제거하면 S는 JJOOII가 됩니다.
Operation 3을 두 번 이하로 사용하여 레벨 K의 JOI 문자열을 만드는 것은 불가능하므로 2를 인쇄해야 합니다.
예제2
93
JJJOOOIII
0
연산을 사용할 필요가 없습니다.
예제3
91
IIIOOOJJJ
-1
이 샘플에서는 문자열 S에서 레벨 1의 JOI 문자열을 만드는 것이 불가능합니다.