Bitaro nhận được một xâu \(S\) dài \(N\) làm quà sinh nhật. Xâu \(S\) chỉ gồm ba loại ký tự J, O và I.

Với mỗi số nguyên dương \(K\), ta gọi xâu gồm đúng \(K\) ký tự J, tiếp theo là \(K\) ký tự O, rồi \(K\) ký tự I là xâu JOI cấp \(K\). Chẳng hạn, JJOOII là xâu JOI cấp \(2\).

Bitaro thích xâu JOI cấp \(K\), nên muốn biến \(S\) thành một xâu như vậy bằng ba thao tác sau, mỗi thao tác có thể thực hiện bao nhiêu lần tùy ý và theo thứ tự bất kỳ:

1. Xóa ký tự đầu tiên của \(S\).
2. Xóa ký tự cuối cùng của \(S\).
3. Xóa một ký tự của \(S\) không phải ký tự đầu tiên hay cuối cùng.

Vì thao tác \(3\) tốn nhiều thời gian, Bitaro muốn dùng thao tác này ít lần nhất có thể. Cho xâu \(S\) dài \(N\) và số nguyên dương \(K\), hãy tìm số lần thực hiện thao tác \(3\) ít nhất để biến \(S\) thành xâu JOI cấp \(K\). Nếu không thể, hãy in ra \(-1\).

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng sau. \(N,K\) là số nguyên và \(S\) là một xâu.

N K
S

Dữ liệu ra

In ra một dòng chứa số lần thực hiện thao tác \(3\) ít nhất cần thiết để tạo xâu JOI cấp \(K\) từ \(S\), hoặc \(-1\) nếu không thể.

Ràng buộc

• \(3 \le N \le 200\,000\).
• \(1 \le K \le \frac{N}{3}\).
• \(S\) có độ dài \(N\) và chỉ gồm các ký tự J, O, I.

Phân nhóm

Mọi nhóm đều tuân theo các ràng buộc chung. Chỉ nhận được điểm của một nhóm nếu vượt qua tất cả bộ dữ liệu trong nhóm đó.

1. \(1\) điểm: \(N \le 21\)
2. \(12\) điểm: \(N \le 3000\)
3. \(87\) điểm: Không có

Ví dụ

10 2
OJIJOIOIIJ

2

9 3
JJJOOOIII

0

9 1
IIIOOOJJJ

-1

Nguồn

Bản dịch tiếng Việt từ đề chính thức bằng tiếng Anh của Ủy ban Olympic Tin học Nhật Bản, vòng chung kết JOI 2019/2020 ngày 9 tháng 2 năm 2020. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.