Villain Robots

The superhero Park Seungwon has finally hacked the villain robots that invaded Earth. Each robot has $N$ vulnerabilities ($1 \le N \le 20$), and the $i$-th vulnerability is described by a string $S_i$ of length at most 15 consisting only of the characters 'A', 'B', and 'C'. Park attacks a robot by pressing the 'A', 'B', and 'C' buttons; every time some contiguous run of the buttons pressed so far exactly matches a vulnerability $S_i$, one attack against that vulnerability succeeds.

For example, suppose the vulnerabilities are "ABA", "CB", and "ABACB". If Park presses "ABACB", then characters 1~3 match "ABA", characters 4~5 match "CB", and the whole string matches "ABACB", so three separate attacks succeed. As this shows, several vulnerabilities can be hit at once, and the same vulnerability can be used more than once. In other words, the number of successful attacks equals the total count of (position, vulnerability) pairs for which a substring of the pressed string equals that vulnerability.

Because Park is short on time, he can press the buttons exactly $K$ times ($1 \le K \le 1000$). Find the maximum number of attacks Park can make succeed.

The first line contains two integers $N$ and $K$ separated by a space. Each of the next $N$ lines contains one vulnerability string $S_i$.

Print, on a single line, the maximum number of attacks Park can make succeed.

When $N = 3$, $K = 7$, and the vulnerabilities are "ABA", "CB", and "ABACB", pressing "ABACBCB" matches "ABA" once, "ABACB" once, and "CB" twice, for a total of 4 successful attacks.