我们所说的“单词”是指由大写英文字母组成的序列。单词的长度即其中包含的字母个数。例如，单词 $\alpha = \text{ABAACBBBA}$ 的长度为 9。单词中的“块”是指由相同字母组成的极大连续子序列。如果一个单词包含 $t$ 个块，则称其为 $t$-hard。对于单词 $\alpha$，它是一个 6-hard 的单词，因为它由以下块组成：$\text{A|B|AA|C|BBB|A}$。

如果两个单词长度相同，我们可以检查它们的差异程度。若两个长度为 $n$ 的单词在恰好 $k$ 个位置 $i$ ($1 \le i \le n$) 上字母不同，则称它们是 $k$-different 的。检查单词 $\alpha$ 和 $\beta = \text{AAAABBBBB}$，可知它们是 3-different 的。

对于给定的单词 $\alpha$，我们希望找到一个差异不太大且结构不太复杂的单词 $\beta$。你的任务是确定 $\beta$ 最简单可以达到什么程度。

编写一个程序：

• 读取整数 $n$、$k$ 以及长度为 $n$ 的单词 $\alpha$；
• 确定 $t$ 的最小值，使得存在一个 $t$-hard 的单词 $\beta$，且 $\beta$ 与 $\alpha$ 的差异不超过 $k$（即不存在 $k' > k$，使得 $\alpha$ 和 $\beta$ 是 $k'$-different 的）；
• 将答案输出到标准输出。

输入格式

第一行包含两个整数 $n$ 和 $k$，用空格隔开 ($1 \le n \le 1\,000$, $0 \le k \le n$)。它们分别代表单词 $\alpha$ 的长度和允许的最大差异程度。第二行包含由 $n$ 个大写字母组成的单词 $\alpha$。

输出格式

输出一个整数，即 $t$ 的最小值。

样例

输入 1

9 3
ABAACBBBA

输出 1

2