题目描述

Byteasar breeds hamsters.

Each hamster has a unique name, consisting of lower case letters of the English alphabet.

The hamsters have a vast and comfortable cage.

Byteasar intends to place a display under the cage to visualize the names of his hamsters.

This display is simply a sequence of letters, each of which can be either lit or not independently.

Only one name will be displayed simultaneously.

The lit letters forming the name have to stand next to each other, i.e., form a contiguous subsequence.

Byteasar wants to be able to display the names of the hamsters on at least different positions.

However, he allows displaying the same name on multiple different positions, and does not require to be able to display each and every hamster's name.

Note that the occurrences of the names on the display can overlap.

You can assume that no hamster's name occurs (as a contiguous fragment) in any other hamster's name.

Bytesar asks your help in determining the minimum number of letters the display has to have.

In other words, you are to determine the minimum length of a string (consisting of non-capital letters of the English alphabet) that has at least total occurrences of the hamsters' names (counting multiplicities).

(We say that a string occurs in the string if forms a contiguous fragment of .)

输入格式

The first line of the standard input holds two integers and (, ), separated by a single space, that denote the number of Byteasar's hamsters and the minimum number of occurrences of the hamsters' names on the display.

Each of the following lines contains a non-empty string of non-capital letters of the English alphabet that is the hamster's name.

The total length of all names does not exceed letters.

输出格式

The first and only line of the standard output should hold a single integer - the minimum number of letters the display has to have.

题目大意

给出 $n$ 个互不包含的字符串，要求你求出一个最短的字符串 $S$，使得这 $n$ 个字符串在 $S$ 中总共至少出现 $m$ 次，问 $S$ 最短是多少。

4 5
monika
tomek
szymon
bernard

23

提示

$1\le n\le 200$，$1\le m\le 10^9$ ，所有字符串的总长 $\le 10^5$。