Hamsters on Display

Byteasar breeds hamsters. Each hamster has a unique name consisting of lowercase letters of the English alphabet. In his vast and comfortable cage, Byteasar wants to install a display under the cage to show the hamster names. The display is a sequence of letters (each of which can be independently lit or not), and at any given time only one hamster name is shown. The lit letters forming the name must appear contiguously.

Byteasar requires that the display be able to show hamster names in at least $$M$$ different positions. Note that the same hamster name may appear in several different positions and not every hamster's name has to be displayed. Occurrences of hamster names in the display may overlap. It is guaranteed that no hamster's name occurs as a contiguous fragment in any other hamster's name.

Your task is to determine the minimum number of letters the display must have. In other words, given a set of hamster names and a positive integer $$M$$, find the minimum length $$L$$ of a string (consisting of lowercase letters) that contains at least $$M$$ total occurrences of the hamster names (counting multiplicities).

For any hamster name $$p$$ with length $$k=|p|$$, let $$w$$ be the length of its longest proper prefix that is also a suffix. Then, if we choose to work with string $$p$$ only, one can construct a string that contains exactly $$X$$ occurrences of $$p$$ with length $$L = k + (X-1)\cdot (k - w).$$

Your answer is the minimum such $$L$$ taken over all given hamster names, for $$X=M$$.

inputFormat

The first line of input contains two integers $$n$$ and $$M$$ where:

• $$n$$ (1 ≤ $$n$$ ≤ 10⁵) is the number of hamster names.
• $$M$$ (1 ≤ $$M$$ ≤ 10⁹) is the required total number of occurrences.

The following $$n$$ lines each contain a non-empty string consisting of lowercase letters representing a hamster's name. It is guaranteed that all names are unique and no hamster's name occurs as a contiguous fragment in any other hamster's name.

outputFormat

Output a single integer — the minimum length of a display string (a string of lowercase letters) that contains at least $$M$$ total occurrences of the hamster names.

sample

1 1
abc

3