[Poi2010]Hamsters

Tz 养了一群仓鼠，每只仓鼠都有一个由英文小写字母组成的名字。现在，Tz 想构造一个字母序列，使仓鼠的名字作为子串出现在该序列中。

对于每个名字，它在字母序列中的每个匹配起始位置均计为一次出现。不同名字或不同起始位置对应的出现次数分别计算，同一个名字出现多次也会重复计数。

保证任意两个仓鼠的名字互不相同，且任意一个仓鼠的名字都不是另一个仓鼠名字的子串。请构造一个字母序列，使所有名字的出现总次数至少为 $m$，并求出该字母序列的最短长度。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示仓鼠的数量和要求达到的名字出现总次数。

接下来 $n$ 行，每行包含一个仅由英文小写字母组成的名字。

输出格式

输出一行一个整数，表示满足条件的最短字母序列长度。

样例输入

4 5
monika
tomek
szymon
bernard

样例输出

23

数据范围

• $1\le n\le 200$；
• $1\le m\le 10^9$；
• 任意两个名字互不相同；
• 任意一个名字都不是另一个名字的子串。

来源与许可

本题为 POI 2010 试题「Hamsters」，题面与测试数据整理自 BZOJ。

样例 1

输入

4 5
monika
tomek
szymon
bernard

输出

23