背景

:::info[题目背景]

战斗仍在继续。

「沉星书库」深处的大厅早已看不出原本的模样。 断裂的石柱横倒在地，古老书架在魔力冲击中化作焦黑的碎片，四处飞散的尘埃与纸页在紊乱的气流里翻卷，仿佛一场无声燃烧的雪。 黑色的冲击一次又一次撕裂地面，又被更耀眼的魔法正面截断；轰鸣声在穹顶下层层回荡，震得人几乎连呼吸都无法平稳下来。

即使有了聚魔石的支撑，局面也依旧没有轻易好转。

那头盘踞在书库中的魔物实在太强了。 它像是早已与此地残存的古老魔力融为一体，越是久战，气息便越发沉重而危险。 菲伦的普通攻击魔法只能勉强维持局势不至于彻底崩塌，休塔尔克也几次试图逼近，却都被对方扩散出的恐怖压迫硬生生逼退回来。 至于芙莉莲，虽然仍旧站在最前方，神色也没有太大变化，但那种迟迟无法将战局拉向终结的僵持，本身就已经足够说明问题。

又一次术式碰撞之后，短暂的间隙终于出现了。

芙莉莲轻轻向后退了半步，银白色的发梢在尚未平息的余波里微微飘起。 她抬起眼，望着高台前方那头仍在缓慢逼近的魔物，目光里第一次浮现出一点若有所思的意味，像是终于从记忆中翻找到了某个尘封已久的答案。

「这样下去，会很麻烦呢。 」她轻声说道。

「还有别的办法吗？」菲伦立刻问。

芙莉莲没有马上回答，只是伸手探入法袍内侧，取出一卷已经十分陈旧的远古卷轴。 卷轴边缘泛着暗黄，封口处的纹样早已磨损得模糊不清，只有最中央那道极古老的术式印记，仍旧透出一种沉静而危险的气息。 那不像是寻常战斗中会被随手使用的魔法，更像是从很久很久以前遗留下来的东西，安静地沉睡在岁月深处，直到此刻才再次被人唤醒。

「这是我以前收集到的一种古代术式。 」芙莉莲平静地说道，「对付这种类型的魔物，应该很有效。 」

休塔尔克望着那卷卷轴，神情却没有轻松多少：「既然这么有效，为什么不一开始就用？」

「因为没那么简单。 」芙莉莲轻轻展开卷轴，低头看了一眼上面复杂而古老的术式文字，「这个魔法本身并不难控制，麻烦的是，想让它发挥出最佳的功效，需要动点脑子。 」

「动点脑子？」菲伦微微一怔。

「嗯。 」芙莉莲点了点头，「古代魔法使总喜欢把关键术式设计成这样。 不同的术式组合能引出不同强度的魔法，组合不好这些术式的话，终究还是打不过的；然而如果能组合好的话，能发挥出真正的远古魔法之力。 」

她的声音依旧平静，可前方那头魔物显然不会体贴地为他们留出太多思考时间。 漆黑的魔力再次在大厅深处汇聚，像风暴来临前不断下压的乌云。 菲伦下意识握紧法杖，休塔尔克也重新站稳脚步，挡在两人身前。 而芙莉莲则低头看着卷轴上逐渐浮现的术式纹路，像是在确认某些极其细微、却又绝不能弄错的条件。

题目描述

远古卷轴可以看作一条很长的纸带，上面写着一个只包含小写英文字母的字符串 $s$，长度为 $n$。

为了最好地发挥出卷轴上远古魔法的威力，芙莉莲需要从这条纸带上挑出恰好 $k$ 段内容完全相同的连续片段。设被挑出的内容是字符串 $t$，这 $k$ 次出现的起始位置分别是$p_1 < p_2 < \cdots < p_k$。

这 $k$ 段可以互相重叠；只要它们在卷轴上的内容完全相同，就算是合法选择。同一个字符串出现在不同位置，算不同的出现。

术式重叠度越高，则能造成的威力越大，芙莉莲定义了「术式叠印得分」为：

• 先把这 $k$ 段片段的长度全部加起来，得到术式叠印长度 $A = k|t|$；
• 再看原卷轴上覆盖这 $k$ 段片段的最短连续区间。这个区间从第一个被选中的片段开头开始，到最后一个被选中的片段结尾结束，得到卷轴长度 $B = p_k - p_1 + |t|$。

于是，这组选择的「术式叠印得分」为 $A - B$。

如果芙莉莲觉得所有方案都不划算，也可以什么都不选，此时「术式叠印得分」记为 $0$。

请你求出最大可能的「术式叠印得分」。

输入格式

输入第一行包含两个整数 $n, k(1\leq n\leq 2\times 10^5, 1\leq k\leq 40)$，代表卷轴上字符串 $s$ 的长度和芙莉莲想挑出的段数。

输入第二行包含一个长度恰好为 $n$ 的字符串 $s$，只包含小写英文字母。

输出格式

输出一行一个整数，表示最大可能的「术式叠印得分」。

7 3
abababa

2

5 3
aaaaa

4

7 4
abacaba

0

提示

对于样例一，可以选择的片段为 aba，位置分别为$1$、$3$、$5$，术式叠印长度为 $3\times 3=9$，卷轴长度为 $5 - 1 + 3 = 7$，则此时「术式叠印得分」为 $2$，可以证明没有更优的选择。

对于样例二，可以选择的片段为 aaa，位置分别为 $1$、$2$、$3$，术式叠印长度为 $3\times 3=9$，卷轴长度为 $3 - 1 + 3 = 5$，则此时「术式叠印得分」为 $4$，可以证明没有更优的选择。

对于样例三，可以选择的片段为 a，位置分别为 $1$、$3$、$5$、$7$，术式叠印长度为 $4\times 1=4$，卷轴长度为 $7 - 1 + 1 = 7$，此时则「术式叠印得分」为$-3$，显然这个方案并不划算，芙莉莲可以选择什么都不选，则「术式叠印得分」为 $0$。

:::info[题目背景]

---

古老卷轴上的最后一道纹路终于彻底亮起。

那一瞬间，原本被黑色魔力与轰鸣填满的大厅，像是忽然被某种更久远、也更沉静的力量按住了。淡金色的光从卷轴表面缓缓扩散开来，沿着芙莉莲的法杖一寸寸流入已经构筑完成的术式之中。那并不是炫目到令人无法直视的光辉，反而安静得近乎肃穆，像某种自漫长岁月彼端降临的回响。可正是这样的力量，让那头魔物第一次真正停滞了一瞬。

「就是现在。」芙莉莲轻声说道。

菲伦立刻抬手，将最后一股聚魔石中的魔力稳稳送入大量的普通攻击魔法；休塔尔克也咬紧牙关，从侧面强行逼近，用尽全力牵制住那头魔物的动作。下一刻，芙莉莲展开的远古魔法彻底落下。庞大而凝练的术式光辉在大厅中央收束成一道近乎笔直的辉线，毫无迟疑地贯穿了那团盘踞已久的黑暗。

没有凄厉的哀鸣，只有一声低沉而漫长的震响。那头魔物胸口暗红色的核心在光辉中寸寸崩裂，漆黑的外壳也随之剥落、瓦解，像风化了数百年的石像终于迎来彻底崩塌。紊乱的气流卷起满地碎纸与石尘，书架残骸在余波中微微震颤，随后，一切都慢慢安静了下来。

大厅里只剩下急促却逐渐平稳的呼吸声。

菲伦放下法杖，指尖还残留着轻微的颤抖；休塔尔克撑着武器站稳身形，长长吐出一口气，仿佛直到此刻才终于确认战斗已经结束。芙莉莲则只是安静地看着前方那片正在散去的黑色残渣，神情依旧平静，像是终于处理掉了一件稍显麻烦的旧事。

「结束了呢。」她轻声说。

短暂整理过行装之后，三人没有在原地停留太久。破碎的大厅后方，一道通往更深处的回廊已经在昏暗中静静显现出来。那里没有风，也没有声音，只有古老石壁之间沉默流淌的微弱魔力。