题目描述

对于由小写英文字母组成的字符串 $T$，考虑以下问题，并设 $f(T)$ 为答案。

执行任意次数以下操作所得到的不同字符串的数量：删除 $T$ 的第一个字符并将其附加到末尾。

给定一个长度为 $N$ 的由小写英文字母组成的字符串 $S$。你可以最多执行 $K$ 次下述操作（可能为零次）：

• 选择 $S$ 中的一个字符，并将其更改为任意小写英文字母。

求在进行操作后 $f(S)$ 的最小可能值。

约束条件

• $1 \le N \le 2000$
• $0 \le K \le N$
• $S$ 是长度为 $N$ 的由小写英文字母组成的字符串。
• $N$ 和 $K$ 是整数。

输入

输入以标准格式给出，格式如下：

$N$ $K$
$S$

输出

输出答案。

示例输入1

4 1
abac

示例输出1

2

如果在第一次操作中将第四个字符 c 更改为 b，我们可以得到 $S=$ abab，其中 $f(S)=2$。

只需进行一次操作，$f(S)$ 不可能变为 $1$ 或更少，因此答案为 $2$。

示例输入2

10 0
aaaaaaaaaa

示例输出2

1

示例输入3

6 1
abcaba

示例输出3

3