Hamsters

Time limit3sMemory limit512 MB

Summary

Find the shortest lowercase string containing at least m occurrences of the given hamster names, counted with multiplicity.

Level: Hard9 of 10
Topics: String matching, Dynamic programming, Graph, Shortest path
Solved: No attempts yet

Problem

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$ .

Input

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$ .

Output

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

Hint

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.

Examples7

Example 1
Input
```
4 5
monika
tomek
szymon
bernard
```
Expected output
```
23
```
Example 2
Input
```
1 1
z
```
Expected output
```
1
```
Example 3
Input
```
1 1000000000
a
```
Expected output
```
1000000000
```
Example 4
Input
```
1 3
aa
```
Expected output
```
4
```
Example 5
Input
```
1 5
aba
```
Expected output
```
11
```
Example 6
Input
```
1 4
abc
```
Expected output
```
12
```
Example 7
Input
```
3 1
apple
bob
cherry
```
Expected output
```
3
```