Bitaro 在生日时收到了一串长度为 $N$ 的字符串 $S$。字符串 $S$ 由 J、O 和 I 三种字符组成。

对于每个正整数 $K$，我们将由 $K$ 个 J、$K$ 个 O 和 $K$ 个 I 按此顺序组成的字符串称为 $K$ 级 JOI 字符串。例如，JJOOII 是 2 级 JOI 字符串。

Bitaro 喜欢 $K$ 级 JOI 字符串，因此他打算通过以下三种操作，以任意顺序执行任意次数，从字符串 $S$ 中制作出一个 $K$ 级 JOI 字符串：

操作 1：Bitaro 删除 $S$ 的第一个字符。 操作 2：Bitaro 删除 $S$ 的最后一个字符。 操作 3：Bitaro 删除 $S$ 中既不是第一个也不是最后一个的字符。

由于使用操作 3 比较耗时，Bitaro 希望以尽可能少的操作 3 次数制作出一个 $K$ 级 JOI 字符串。

请编写一个程序，给定长度为 $N$ 的字符串 $S$ 和正整数 $K$，输出制作 $K$ 级 JOI 字符串所需的最少操作 3 次数。如果无法通过这些操作制作出 $K$ 级 JOI 字符串，则输出 $-1$。

输入格式

从标准输入读取以下数据。$N$ 和 $K$ 为整数，$S$ 为字符串。

$N \ K$ $S$

输出格式

输出一行到标准输出。该输出应包含制作 $K$ 级 JOI 字符串所需的最少操作 3 次数。如果无法制作出 $K$ 级 JOI 字符串，则输出 $-1$。

数据范围

• $3 \le N \le 200\,000$
• $1 \le K \le \frac{N}{3}$
• $S$ 是一个长度为 $N$ 的字符串，由 J、O 和 I 组成。

子任务

1. (1 分) $N \le 21$。
2. (12 分) $N \le 3\,000$。
3. (87 分) 无附加限制。

样例

样例输入 1

10 2
OJIJOIOIIJ

样例输出 1

2

说明 1

你可以通过以下操作从字符串 $S$ 制作出 $K$ 级 JOI 字符串： 1. 使用操作 1，$S$ 变为 JIJOIOIIJ。 2. 使用操作 2，$S$ 变为 JIJOIOII。 3. 使用操作 3 删除第二个字符，$S$ 变为 JJOIOII。 4. 使用操作 3 删除第四个字符，$S$ 变为 JJOOII。 无法通过少于两次操作 3 制作出 $K$ 级 JOI 字符串，因此应输出 2。

样例输入 2

9 3
JJJOOOIII

样例输出 2

0

说明 2

你不需要使用任何操作。

样例输入 3

9 1
IIIOOOJJJ

样例输出 3

-1

说明 3

在此样例中，无法从字符串 $S$ 制作出 1 级 JOI 字符串。