← 返回题目列表

Codeforces · 178/F3

F3. 代表性抽样

中文机器翻译题面 查看原题

ABBYY 的 Smart Beaver 与“细胞学与遗传学研究所”有着悠久的合作历史。最近,研究所工作人员向海狸提出了一个新问题。问题如下。

有 n 个蛋白质的集合(不一定不同)。每个蛋白质都是由小写拉丁字母组成的字符串。科学家们向海狸提出的问题是从最初的蛋白质集合中选择大小为 k 的子集合,以使所选蛋白质子集合的代表性最大化。

ABBYY 的 Smart Beaver 进行了一些研究,得出的结论是,可以通过简单计算的单个数字来评估一组蛋白质的代表性。假设我们有一个由 k 个描述蛋白质的字符串组成的集合 {a1, ..., ak}。该集合的代表性值为以下值:

$$\sum_{i=1}^{k-1}\sum_{j=i+1}^{k}f(a_i,a_j),$$

其中f(x, y)是字符串x和y的最长公共前缀的长度;例如,f("abc", "abd") = 2,f("ab", "bcd") = 0。

因此,蛋白质集合{“abc”,“abd”,“abe”}的代表性等于6,而集合{“aaa”,“ba”,“ba”}的代表性等于2。

发现这一点后,ABBYY 的 Smart Beaver 要求杯赛参赛者编写一个程序,从给定的蛋白质集合中选择一个大小为 k 的子集合,该子集合具有最大可能的代表性值。帮他解决这个问题吧!

输入

第一个输入行包含两个整数 n 和 k (1 ≤ k ≤ n),用一个空格分隔。接下来的 n 行包含蛋白质的描述,每行一个。每个蛋白质都是一个不超过 500 个字符的非空字符串,仅由小写拉丁字母 (a...z) 组成。有些字符串可能是相等的。

获得 20 点的输入限制为:

- 1 ≤ n ≤ 20

获得 50 点的输入限制为:

- 1 ≤ n ≤ 100

获得 100 点的输入限制为:

- 1 ≤ n ≤ 2000

输出

打印一个数字,表示给定蛋白质集合的大小为 k 的子集合可以具有的最大可能的代表性值。

示例

输入 #1

3 2
aba
bzd
abq

输出 #1

2

输入 #2

4 3
eee
rrr
ttt
qqq

输出 #2

0

输入 #3

4 3
aaa
abba
abbc
abbd

输出 #3

9