P3041 [USACO12JAN] Video Game G

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?

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 a single integer representing the answer.

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