Byteasar 饲养了仓鼠。每只仓鼠都有一个独特的名字，由小写英文字母组成。仓鼠们住在一个宽敞舒适的笼子里。Byteasar 打算在笼子下方放置一个显示屏，用来显示他仓鼠的名字。这个显示屏本质上是一个字母序列，每个字母都可以独立地处于点亮或熄灭状态。同一时间只能显示一个名字。被点亮的、组成名字的字母必须彼此相邻，即形成一个连续的子序列。

Byteasar 希望能够在至少 $m$ 个不同的位置显示仓鼠的名字。他允许在多个不同的位置显示同一个名字，也不要求必须能够显示每一只仓鼠的名字。注意，名字在显示屏上的出现位置可以重叠。你可以假设没有任何一只仓鼠的名字是另一只仓鼠名字的子串（作为连续片段）。Byteasar 请求你帮助确定显示屏最少需要多少个字母。

换句话说，你需要确定一个字符串（由小写英文字母组成）的最小长度，使得该字符串中包含至少 $m$ 次仓鼠名字的出现（计算重叠情况）。（如果字符串 $s$ 是字符串 $t$ 的连续片段，则称 $s$ 在 $t$ 中出现。）

输入格式

标准输入的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 200$，$1 \le m \le 10^9$），由一个空格分隔，分别表示 Byteasar 拥有的仓鼠数量和显示屏上名字出现的最少次数。接下来的 $n$ 行，每行包含一个非空字符串，由小写英文字母组成，代表仓鼠的名字。所有名字的总长度不超过 100,000 个字母。

输出格式

标准输出的第一行应仅包含一个整数，即显示屏最少需要的字母数量。

样例

输入 1

4 5
monika
tomek
szymon
bernard

输出 1

23

说明 1

最短的显示屏可以是，例如：szymonikatomekszymonika。它总共包含了 5 次仓鼠名字的出现：szymon 和 monika 各出现了两次，tomek 出现了一次，而 bernard 没有出现。