拼接

资料馆中有 $n$ 段互不相同的关键片段 $s_1, s_2, \ldots, s_n$ 。保证不存在某段片段是另一段片段的连续子串。

现在需要整理出一份只由小写英文字母组成的记录 $T$ 。若某个片段 $s_i$ 在 $T$ 的某个位置作为连续子串出现，则记为一次出现。同一个片段在不同位置的出现分别计数，不同片段的出现也可以重叠。

要求 $s_1, s_2, \ldots, s_n$ 在 $T$ 中出现次数之和至少为 $m$ 。

求满足要求的 $T$ 的最小长度。

输入格式

第一行两个整数 $n,m$ 。

接下来 $n$ 行，每行一个非空字符串 $s_i$ 。

一行一个整数，表示 $T$ 的最小长度。

5 100
a
b
c
d
e

令 $T$ 为长度 $100$ 的全 $\text{a}$ 串。每个位置上的字符都会使对应的单字符片段出现一次，因此最小长度为 $100$ 。

4 5
ab
bc
cd
de

取 $T=\texttt{abcdebc}$ ，其中 $\texttt{ab},\texttt{bc},\texttt{cd},\texttt{de},\texttt{bc}$ 共出现 $5$ 次，长度为 $7$ 。

可以证明不存在长度更短的合法记录。

本题共 $20$ 组数据。

对于前 $30\%$ 的数据， $n \le 5$ ， $m \le 5$ ，每个字符串长度不超过 $5$ 。

对于前 $60\%$ 的数据， $n \le 50$ ， $m \le 1000$ 。

对于 $100\%$ 的数据， $1 \le n \le 200$ ， $1 \le m \le 10^9$ ，所有字符串的总长度不超过 $10^5$ ，字符串由小写英文字母组成。