时间限制： 1.0 秒

空间限制： 256 MB

问题描述

小明最近在研究一门新的语言，叫做 Q 语言。Q 语言单词和文章都可以用且仅用只含有小写英文字母的字符串表示，任何由这些字母组成的字符串也都是一篇合法的 Q 语言文章。

在 Q 语言的所有单词中，小明选出了他认为最重要的 $n$ 个。使用这些单词，小明可以评价一篇 Q 语言文章的“重要度”。

文章“重要度”的定义为：在该文章中，所有重要的 Q 语言单词出现次数的总和。其中多次出现的单词，不论是否发生包含、重叠等情况，每次出现均计算在内。

例如，假设 $n = 2$，小明选出的单词是 gvagv 和 agva。在文章 gvagvagvagv 中，gvagv 出现了 $3$ 次，agva 出现了 $2$ 次，因此这篇文章的重要度为 $3+2=5$。

现在，小明想知道，一篇由 $m$ 个字母组成的 Q 语言文章，重要度最高能达到多少。

输入格式

从标准输入读入数据。

输入的第一行包含两个整数 $n, m$，表示小明选出的单词个数和最终文章包含的字母个数。

接下来 $n$ 行，每行包含一个仅由英文小写字母构成的字符串，表示小明选出的这 $n$ 个单词。

输出格式

输出到标准输出。

输出一行一个整数，表示由 $m$ 个字母组成的 Q 语言文章中，重要度最高的文章的重要度。

3 15
agva
agvagva
gvagva

11

样例 1 解释

$15$ 个字母组成的重要度最高的文章为 gvagvagvagvagva。

在这篇文章中，agva 出现 $4$ 次，agvagva 出现 $3$ 次，gvagva 出现 $4$ 次，共计 $4+3+4=11$ 次。

评测用例规模与约定

在评测时将使用 $10$ 个评测用例对你的程序进行评测。

设 $s$ 为构成 $n$ 个重要单词字母的总个数，例如在样例中，$s=4+7+6=17$；$a$ 为构成 $n$ 个重要单词字母的种类数，例如在样例中，共有 $3$ 中字母 a, g, v，因此 $a=3$。

评测用例 $1$ 和 $2$ 满足 $2 \le n \le 3,~1500 \le m \le 2000,~s = 40$；

评测用例 $3$ 和 $4$ 满足 $m = 20,~2 \le a \le 3$；

评测用例 $5$、$6$ 和 $7$ 满足 $2000 \le m \le 100000$；

评测用例 $8$ 满足 $n = 2$；

所有的评测用例满足 $1 \le s \le 100,~1 \le m \le 10^{15}$，每个单词至少包含 $1$ 个字母，保证单词中仅出现英文小写字母，输入中不含多余字符，不会出现重复的单词。