Description

Bessie is playing a game with only three skill keys A, B, C available, and these keys can form $n$ specific combos. The $i$-th combo is represented by a string $s_i$.

Bessie will input a string $t$ of length $k$, and each time a combo appears in $t$, Bessie scores one point. An occurrence of $s_i$ in $t$ means that $s_i$ is a contiguous substring of $t$ starting at some position. If $s_i$ is a contiguous substring starting at multiple positions in $t$, it is counted multiple times.

If Bessie inputs exactly $k$ characters, what is the maximum score she can get?

Input Format

The first line contains two integers, the number of combos $n$ and the number of characters Bessie inputs $k$.

Then $n$ lines follow, each containing a string $s_i$ representing a combo.

Output Format

Output a single integer representing the answer.

3 7 
ABA 
CB 
ABACB 

4 

Hint

Sample 1 Explanation.

If Bessie inputs ABACBCB, then ABA appears once, ABACB appears once, and CB appears twice, for a total of $4$ points. This can be proven optimal.

Constraints

For all testdata, it is guaranteed that:

• $1 \le n \le 20$, $1 \le k \le 10^3$.
• $1 \le |s_i| \le 15$. Here $|s_i|$ denotes the length of string $s_i$.
• All strings contain only the uppercase letters A, B, C.

Translated by ChatGPT 5