問題文

英小文字からなる文字列 $T$ に対して次の問題を考え、その答えを $f(T)$ とします。

$T$ の先頭の文字を削除し末尾に追加する操作を任意の回数行うことによって作ることのできる文字列の種類数を求めてください。

英小文字からなる長さ $N$ の文字列 $S$ が与えられます。あなたは以下の操作を $K$ 回以下行うことが出来ます。($1$ 回も行わなくてもよいです。)

• $S$ の文字を $1$ 個選び、任意の英小文字に変更する。

操作終了後の $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

$1$ 回目の操作で $4$ 文字目を c から b に変更すると $S=$ abab となり、$f(S)=2$ となります。

$f(S)$ を $1$ 回以下の操作で $1$ 以下にすることはできないため、答えは $2$ です。

入力例 2

10 0
aaaaaaaaaa

出力例 2

1

入力例 3

6 1
abcaba

出力例 3

3