题目描述

给定一个长度为 $N$ 的字符串，只包含大写英文字母，并给定整数 $K$。

你可以反复执行如下操作：

• 选择当前字符串中一段长度至少为 $K$ 的连续子串；
• 这段子串的所有字符必须相同；
• 将这段子串从字符串中删除，剩余部分拼接起来。

操作可以持续进行，直到字符串为空，或当前字符串中不存在长度至少为 $K$ 的相同字符连续段。

任务

求通过合理选择删除顺序后，最终字符串长度的最小可能值。

输入格式

第一行包含两个整数 $N,K$。

第二行包含一个长度为 $N$ 的字符串，由大写英文字母组成。

输出格式

输出一个整数，表示最终字符串的最小可能长度。

数据范围与限制

• $1\le K\le N\le 500$

子任务：

• 10 分：$25\le K\le N\le 100$
• 10 分：$K=2$
• 10 分：字符串中不同字符个数为 2
• 15 分：$1\le N\le 50$
• 35 分：$1\le N\le 200$

样例

输入

10 3
AAABBBCCCA

输出

0

样例解释

可以先删除 [4,6] 的 BBB，字符串变为 AAACCCA；再删除 CCC，得到 AAAA；最后删除长度为 4 的 AAAA，字符串为空。

如果一开始先删除 [1,3] 的 AAA，之后删除 CCC，最终会剩下一个 A，不是最优。