P3502 [POI 2010] CHO-Hamsters

Byteasar 养了许多仓鼠。 每只仓鼠都有一个唯一的名字，由小写英文字母组成。 这些仓鼠有一个宽敞舒适的笼子。 Byteasar 打算在笼子下方放置一个显示器，以可视化显示他仓鼠的名字。 这个显示器只是一个字母序列，每个字母可以独立地亮起或不亮起。 同时只会显示一个名字。 亮起的字母必须相邻，即形成一个连续的子序列。 Byteasar 希望能够在至少 $m$ 个不同的位置显示这些仓鼠的名字。 然而，他允许在多个不同的位置显示相同的名字，并且不要求能够显示每一个仓鼠的名字。 注意，名字在显示器上的出现可以重叠。 可以假设没有任何仓鼠的名字会作为连续片段出现在其他仓鼠的名字中。 Byteasar 请求你帮助确定显示器需要的最小字母数。 换句话说，你需要确定一个字符串的最小长度（由非大写英文字母组成），使得仓鼠名字的总出现次数（计入重复）至少为 $m$。 （我们说字符串 $A$ 出现在字符串 $B$ 中，如果 $A$ 形成 $B$ 的一个连续片段。）

标准输入的第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 200$, $1 \le m \le 10^9$)，用一个空格分隔，表示 Byteasar 的仓鼠数量和显示器上仓鼠名字出现的最小次数。 接下来的 $n$ 行中的每一行包含一个非空的非大写英文字母字符串，表示仓鼠的名字。 所有名字的总长度不超过 $10^5$ 个字母。

标准输出的第一行应包含一个整数——显示器需要的最小字母数。

$1 \le n \le 200$，$1 \le m \le 10^9$，所有字符串的总长 $\le 10^5$。 题面翻译由 ChatGPT-4o 提供。