CCC2009 Dinner之Zuma2

类似于祖玛游戏，给定一排 $N$ 个珠子，已知每个珠子的颜色（原题中颜色只有 $2$ 种），以及一个整数 $K$。

问你最少进行多少次操作，可以把这些珠子全部消去。每次操作是：选择连续的一段，它们必须包含同一种颜色，并且长度不小于 $K$，将它们消去，左右两边的珠子合并（不会自动消去，产生链式反应）。

如果不能完成，输出 $-1$ 即可。

输入格式

第一行两个整数 $N$ 和 $K$。

第二行一个长度为 $N$ 的字符串，表示每个珠子的颜色。

输出格式

一行一个整数，表示最少的操作次数；如果无法把珠子全部消去，输出 $-1$。

样例输入

7 2
GHHGHHG

样例输出

3

样例解释

先消去第一对 HH，剩下 GGHHG；再消去剩下的一对 HH，剩下 GGG；最后一次把这 $3$ 个 G 一起消去。总共 $3$ 次操作。

数据范围

• $N\le 100$；
• $K\le 6$；
• 原题中珠子的颜色只有 $2$ 种。

来源与许可

本题为 CCC 2009 试题「Dinner 之 Zuma2」，题面与测试数据整理自 BZOJ 2220。

样例 1

输入

7 2
GHHGHHG

输出

3