#arc140a. [arc140_a]Right String

[arc140_a]Right String

题目描述

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

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

给定一个长度为 NN 的由小写英文字母组成的字符串 SS。你可以最多执行 KK 次下述操作(可能为零次):

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

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

约束条件

  • 1N20001 \le N \le 2000
  • 0KN0 \le K \le N
  • SS 是长度为 NN 的由小写英文字母组成的字符串。
  • NNKK 是整数。

输入

输入以标准格式给出,格式如下:

NN KK
SS

输出

输出答案。

示例输入1

4 1
abac

示例输出1

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

只需进行一次操作,f(S)f(S) 不可能变为 11 或更少,因此答案为 22

示例输入2

10 0
aaaaaaaaaa

示例输出2

示例输入3

6 1
abcaba

示例输出3