配点: 100 点
Bitaro 从他的朋友 Vivako 那里收到了一份生日礼物。 J,O,I 的 3 由类型字符组成的长度 N 字符串
我收到了 S 。
必须是大于或等于
K 在 1 的整数。K 字符
按此顺序排列的 J,K 字符
按此顺序排列的 O,K 字符
按此顺序排列的 I 字符串是等级 K 的 JOI 字符串
我们称之为。例如,JJOOII 是级别
这是 2 的 JOI 字符串。
Bitaro 已等级 我喜欢 K 的 JOI 字符串,所以以下 通过以任意顺序执行任意次数的 3 类型的操作,您可以创建一个字符串 S 级别 我决定将其转换为 K 的 JOI 字符串。 删除
- 操作 1 文字列 S 的第一个字符。 删除
- 操作 2 文字列 S 的最后一个字符。 删除既不是
- 操作 3 文字列 S 开头也不是结尾的字符。
操作 3 很乏味,所以 3 执行尽可能少的次数来创建字符串 我想将其转换为 S 级别 我决定将其转换为 K 的 JOI 字符串。 大于或等于
长度为 N 字符串 我收到了 S 和 在 1 的整数 给定 K ,字符串 转换为 S 级别 我决定将其转换为 K 的 JOI 字符串所需的操作 编写一个程序,输出次数 3 的最小值。但是,无论您如何执行操作,字符串 如果无法转换为 S 级别 我决定将其转换为 K 的JOI字符串,则改为 输出 −1 。
入力
输入是按以下格式从标准输入给出的。N, K 是一个整数。S 是一个字符串。 最小次数
N K S
出力
文字列 S 级别 我决定将其转换为 K 的 JOI 字符串所需的操作 编写一个程序,输出次数 3 是 输出为 1 行。但是,无论您如何执行操作,字符串 它是一个 S 级别 我决定将其转换为 K 的JOI字符串,则改为 输出 -1 。
制約
- 3 \leqq N \leqq 200\,000.
- 1 \leqq K \leqq \frac{N}{3}.
- S 是
给出了
J,O,I的 3 由类型字符组成的长度 N 字符串。
小課題
- (1 点) N \leqq 21.
- (12 点) N \leqq 3\,000.
- (87 点)没有额外的限制。
入力例 1
10 2 OJIJOIOIIJ
出力例 1
2
通过执行以下操作,字符串 可以将其转换为 S 级别 我决定将其转换为 K 的JOI字符串。
- 一、操作
执行 1 。字符串
它变成 S 是
给出了
JIJOIOIIJ。 - 下一步操作 2 。字符串
它变成 S 是
给出了
JIJOIOII。 - 下一步操作 3 并从头开始。 2 删除第一个字符。字符串 S 是
给出了
JJOIOII。 - 上次操作
少于 3 并从头开始。 4 删除第一个字符。字符串 S 是
给出了
JJOOII。
2 操作 无法用 3 进行转换,所以 输出2 。
入力例 2
9 3 JJJOOOIII
出力例 2
0
无需任何操作。
入力例 3
9 1 IIIOOOJJJ
出力例 3
-1
在这个输入示例中,无论你如何操作,字符串 无法转换为 S 级别 我决定将其转换为 1 的 JOI 字符串。