#P2085. [Poi2010]Hamsters

[Poi2010]Hamsters

题目描述

给定 nn 个互不相同的仓鼠名字。每个名字只包含小写英文字母。保证任何名字都不作为另一个名字的连续子串出现。

找一个尽量短的只含小写英文字母的字符串,使其中所有仓鼠名字作为连续子串出现的总次数至少为 mm。同一名字在不同起始位置的出现分别计数,各次出现可以重叠。无需让每个名字都出现。

输入格式

第一行两个整数 n,mn,m(1≤n≤2001\le n\le200,1≤m≤1091\le m\le10^9)。

接下来 nn 行,每行一个非空的仓鼠名字。所有名字的长度之和不超过 10510^5。

输出格式

输出一个整数,表示满足条件的字符串的最短长度。

样例

4 5
monika
tomek
szymon
bernard

23

题目来源