给定一个长度为 $$$n$$$ 的字符串 $$$s$$$ 和整数 $$$k$$$ ($$$1 \le k \le n$$$)。字符串$$$s$$$有一个级别$$$x$$$,如果$$$x$$$是最大的非负整数,这样就可以在$$$s$$$中找到:
- $$$x$$$ 长度为 $$$k$$$ 的非相交(非重叠)子串,
- 这些 $$$x$$$ 子字符串的所有字符都是相同的(即每个子字符串仅包含一个不同的字符,并且该字符对于所有子字符串都是相同的)。
子字符串是连续(相邻)字符的序列,它由两个整数 $$$i$$$ 和 $$$j$$$ 定义($$$1 \le i \le j \le n$$$),表示为 $$$s[i \dots j]$$$ = "$$$s_{i}s_{i+1} \dots s_{j}$$$"。
例如,如果 $$$k = 2$$$,则:
- 字符串“aabb”的级别为$$$1$$$(您可以选择子字符串“aa”),
- 字符串“zzzz”和“zzbzz”的级别为$$$2$$$(您可以在每个字符串中选择两个不相交的子字符串“zz”),
- 字符串“abed”和“aca”的级别为$$$0$$$(您无法找到至少一个长度为$$$k=2$$$且包含唯一不同字符的子字符串)。
Zuhair 为您提供了整数 $$$k$$$ 和长度为 $$$n$$$ 的字符串 $$$s$$$。您需要找到 $$$x$$$,即字符串 $$$s$$$ 的级别。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) - 字符串的长度和 $$$k$$$ 的值。
第二行包含长度为 $$$n$$$ 的字符串 $$$s$$$,仅由小写拉丁字母组成。
输出
打印单个整数 $$$x$$$ — 字符串的级别。
示例
输入 #1
8 2 aaacaabb
输出 #1
2
输入 #2
2 1 ab
输出 #2
1
输入 #3
4 2 abab
输出 #3
0
注意
在第一个示例中,我们可以选择$$$2$$$由字母'a'组成的不相交子串:“(aa)ac(aa)bb”,因此级别为$$$2$$$。
在第二个示例中,我们可以选择子字符串“a”或“b”来获得答案$$$1$$$。