Hamsters

Byteasar breeds hamsters. Each hamster has a unique name made of lowercase English letters. He wants to build a display below their cage to show the names. The display is a row of letter cells, each of which can be lit or unlit independently. At any moment the display shows exactly one name: the lit cells that spell the name must be adjacent, forming a contiguous block of the display.

Byteasar wants the display to be long enough that the hamster names can be shown at at least $m$ different positions in total. The same name may be shown at several positions, occurrences of names may overlap, and it is not required that every hamster's name can be shown. It is guaranteed that no hamster's name appears as a contiguous fragment of any other hamster's name.

Equivalently, find the minimum length of a string of lowercase English letters that contains at least $m$ occurrences of the hamster names in total (counting multiplicity). A string $s$ occurs in a string $t$ if $s$ is a contiguous fragment of $t$.

The first line contains two integers $n$ and $m$ ($1 \le n \le 200$, $1 \le m \le 10^9$), separated by a single space: the number of hamsters and the required total number of name occurrences. Each of the next $n$ lines contains one non-empty string of lowercase English letters, a hamster's name. The total length of all names does not exceed $100{,}000$.

Print a single integer: the minimum number of cells the display must have.

For the sample, one shortest display is szymonikatomekszymonika, of length $23$. It contains $5$ name occurrences in total: szymon and monika each occur twice, tomek occurs once, and bernard does not occur at all.