当前没有测试数据。

题目描述

今天是 lkj 的生日，他邀请了他的朋友来他家聚会。聚会上共有 $k$ 个人。lkj 会从一块蛋糕上切下一段发给每个人。这块蛋糕呈长条形，上面从左到右插了 $n$ 根蜡烛。蜡烛共有 $26$ 种颜色，分别用小写字母 a 到 z 表示。lkj 会把蛋糕分成 $k$ 个非空连续段。对于每个连续段，将其从左到右看作一个字符串 $s$，则其美观度定义为：

其中 $s_{[l,r]}$ 为 $s$ 的左端点为 $l$，右端点为 $r$ 的子串。$f(s,t)$ 为同时是 $s,t$ 的子串的本质不同的非空串的数量。

如果段与段之间的美观度差距过大，朋友们会感到愤怒。所以 lkj 想要知道在所有划分方案中，美观度最大的段的美观度最小是多少。

输入格式

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

第二行一个长度为 $n$ 的字符串 $s$，表示蛋糕上蜡烛的颜色。

输出格式

输出一行一个数，表示答案。

样例

10 3
ababababab

11

26 1
littlecyanfishisxiaoqingyu

260

数据范围

对于所有数据，$1\leq k\leq n\leq 5\times 10^4$，$s$ 只包含小写字母。