题目内容

塔子哥是一个喜欢安静的程序员，但他的室友却是一个爱说爱笑的应急食品。为了不被室友的声音打扰，塔子哥自己设计了一副神奇的耳机，可以将外界的噪声转换成一些数字，然后用一种算法来过滤掉。你很好奇这种耳机是如何工作的，于是塔子哥向你介绍了他的算法。

他的算法是这样的：首先，他将外界的声音转录成一个只包含小写字母的字符串 s ，然后计算这个字符串的权值 w(s) ，定义为 s 的长度乘以 s 中不同字母的个数。例如，$w(“abacb”) = 5 * 3 = 15$ 。然后，他将 s 切分成 k 个连续的子串 s1, s2, …, sk ，使得这 k 个子串中权值最大的那个尽可能小。这样，他就可以忽略掉那些权值较大的子串，只关注那些权值较小的子串，从而达到过滤噪声的目的。

你想试试这种算法，于是你输入了一个字符串 s 和一个正整数 k ，表示你想将 s 切分成 k 个子串。你需要输出切分后权值最大的子串的权值。你可以假设 s 的长度不超过 500000 ，且 k 不超过 s 的长度。

样例$1$

输入

adadasda
3

输出

8