因无意中惹恼了掌管天空的神祗，作为惩罚，艾德被流放到了异世界。与原来的世界相比，异世界的语言同样是用 $26$ 个小写英文字母来传达信息；但不同之处在于，其信息的表达并不依赖于断句。但如果一个句子包含的信息量过大，则会让人无法接受。具体来说，对于两个字符串 $s_1,s_2$，定义 $w(s_1,s_2)$ 为有多少个不同的字符串是 $s_1,s_2$ 的公共子串，那么对于一个长度为 $m$ 的句子 $t$，设 $t[l, r]$ 表示 $t$ 中第 $l$ 个字符到第 $r$ 个字符组成的字符串，下标从 $1$ 开始，则其包含的信息量为 $$ val(t) = \sum_{i=1}^{m-1} w^2(t[1,i],t[i+1,m]) $$ 好不容易适应异世界生活的艾德，凭借着自己以往的算法学习经历，应聘到了仅在异世界才有的职业——文章分割者。他每天的任务就是把文章分隔成一个个句子。为了保持美观，一篇文章中的句子数量必须恰好为 $k$。艾德要做的就是在满足上述条件下，使信息量最大的句子中包含的信息量尽可能少，以增强文章的可读性。
为了实现逃离异世界的计划，艾德需要去寻找散落在各地的时间碎片。但为了能够继续在异世界生存，他又不能丢掉这份工作，于是他找到了你来帮助他通过每天的任务检查。具体来说，你只需要对每篇文章回答，在使得信息量最大的句子中包含的信息量尽可能少的条件下，分割后所有句子中最大的信息量是多少。
输入格式
第一行包含两个整数 $n,k$，表示文章的长度以及需要划分出的句子数。
第二行包含一个长度为 $n$ 且仅由小写字母组成的文章 $t$。
输出格式
输出一行一个整数表示分割后句子中最大的信息量。
样例数据
样例 1 输入
10 3
ababababab样例 1 输出
11样例 2 输入
15 2
abcabcddcbacbad样例 2 输出
57子任务
对于所有数据，$1 \leq n \leq 5 \times 10^4, 1 \leq k \leq n$。保证答案不超过 $10^{18}$。
- Subtask 1(10 pts): $n \leq 10$
- Subtask 2(10 pts): $n \leq 50$
- Subtask 3(20 pts): $n \leq 200$
- Subtask 4(20 pts): $n \leq 1000$
- Subtask 5(40 pts): No additional constraints.