题目描述

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

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

你想试试这种算法，于是你输入了一个字符串 s 和一个正整数 k ，表示你想将 s 切分成 k 个子串。你需要输出切分后权值最大的子串的权值。

输入描述

第一行输入一个长度为$n$的字符串$s$，$1\le n\le 10^5$

第二行输入一个整数$k$，其中$1\le k\le n$

输出描述

输出一个整数，表示切分成$k$个子串中权值最大的子串的权值

样例

输入

adadasda
3

输出

8