小红面前有一堵长度为 的墙，用一个只由 （白色）和 （红色）组成的字符串 表示。她希望最终将整面墙全部染成红色。 为此她请来了魔法师小苯。一次施法的流程如下： 小苯选择一个闭区间 ； 立刻将区间内的所有格子染成红色。 小苯至多施法 次，且每次施法的区间长度 不得超过 。 现在小苯想知道，将整堵墙染成红色所需的最小 是多少。请你求出这个 的最小可能值。

输入描述:

输入包含两行。第一行输入两个正整数 ——墙的长度与小苯允许施法的最大次数。第二行输入一个长度为 的字符串 ，保证 仅由字符 与 组成。

输出描述:

输出一个正整数，表示满足要求的最小 。