题目描述

ABBYY 的聪明海狸与"细胞学与遗传学研究所"合作已有很长历史。最近，研究所的工作人员给海狸出了一道新题，内容如下。

现有 $n$ 份蛋白质（不一定互不相同），每份蛋白质是一个由小写拉丁字母组成的字符串。科学家们给海狸出的任务是：从这些蛋白质中选出大小为 $k$ 的子集，使所选蛋白质子集的"代表性"最大。

ABBYY 的聪明海狸研究了半天，得出结论：蛋白质集合的代表性可以用一个数值来评价。设有一个由 $k$ 个字符串组成的集合 $\{a_1, \ldots, a_k\}$，它的代表性为：

其中 $f(x, y)$ 是字符串 $x$ 与 $y$ 的最长公共前缀长度。例如 $f(\text{"abc"}, \text{"abd"}) = 2$，$f(\text{"ab"}, \text{"bcd"}) = 0$。

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

于是，聪明海狸请参赛选手写一个程序：从给定的蛋白质集合中选出大小为 $k$ 的子集，使代表性的值最大。请帮他解决这个问题！

输入格式

输入的第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 2000$），用单个空格隔开。接下来 $n$ 行每行描述一份蛋白质。每份蛋白质是一个非空、长度不超过 500 的纯小写拉丁字母（a…z）字符串。部分字符串可能相同。

获得 20 分的数据满足：$1 \le n \le 20$； 获得 50 分的数据满足：$1 \le n \le 100$； 获得 100 分的数据满足：$1 \le n \le 2000$。

输出格式

输出一个数——从给定蛋白质集合中选出大小为 $k$ 的子集所能达到的最大代表性。

3 2
aba
bzd
abq

2

4 3
eee
rrr
ttt
qqq

0

4 3
aaa
abba
abbc
abbd

9