题目描述

我们称长度不小于 $2$ 且首尾相同的一个字符串为轮回字符串。

给定一个长度为 $n$ 的字符串，你可以更改不超过 $k$ 个字符，使得最后不同轮回子串的数量最大。

两个不同的子串的定义为它们在原字符串的下标区间不同。

输入格式

第一行两个整数 $n,k$。

第二行一个由大小写字母组成的字符串，长度为 $n$。

输出格式

输出最后轮回子串数量的最大值。

样例 #1

样例输入 #1

5 1
abcab

样例输出 #1

4

样例 #2

样例输入 #2

6 3
aabbcc

样例输出 #2

10

提示

样例解释

样例 1

abaab 有 $4$ 个轮回子串，可以证明不存在更大方案。

样例2

aaaaac 有 $10$ 个轮回子串。

有其他构造方式，但结果不会大于 $10$。

数据范围

对于 $25\%$ 的数据，$k=0$。

对于 $100\%$ 的数据，$0\leq k\leq n,1\leq n\leq 5\times 10^5$。