# [POI2010] CHO-Hamsters

## 题目描述

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 ![](http://main.edu.pl/images/OI17/cho-en-tex.1.png) 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 ![](http://main.edu.pl/images/OI17/cho-en-tex.2.png) total occurrences of the hamsters' names (counting multiplicities). (We say that a string ![](http://main.edu.pl/images/OI17/cho-en-tex.3.png) occurs in the string ![](http://main.edu.pl/images/OI17/cho-en-tex.4.png) if ![](http://main.edu.pl/images/OI17/cho-en-tex.5.png) forms a contiguous fragment of ![](http://main.edu.pl/images/OI17/cho-en-tex.6.png).)

## 输入输出格式

### 输入格式

The first line of the standard input holds two integers ![](http://main.edu.pl/images/OI17/cho-en-tex.7.png) and ![](http://main.edu.pl/images/OI17/cho-en-tex.8.png) (![](http://main.edu.pl/images/OI17/cho-en-tex.9.png), ![](http://main.edu.pl/images/OI17/cho-en-tex.10.png)), 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 ![](http://main.edu.pl/images/OI17/cho-en-tex.11.png) 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 ![](http://main.edu.pl/images/OI17/cho-en-tex.12.png) 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.

## 输入输出样例

### 输入样例 #1

``````4 5
monika
tomek
szymon
bernard``````

### 输出样例 #1

``23``

## 说明

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