Migrated from Lutece 554 Video Game Combos

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Bessie is playing a video game! In the game, the three letters A, B, and C are the only valid buttons. Bessie may press the buttons in any order she likes; however, there are only $N$ distinct combos possible ($1 \leq N \leq 20$). Combo $i$ is represented as a string $S_i$ which has a length between $1$ and $15$ and contains only the letters A, B, and C.

Whenever Bessie presses a combination of letters that matches with a combo, she gets one point for the combo. Combos may overlap with each other or even finish at the same time! For example if $N = 3$ and the three possible combos are ABA, CB, and ABACB, and Bessie presses ABACB, she will end with $3$ points. Bessie may score points for a single combo more than once.

Bessie of course wants to earn points as quickly as possible. If she presses exactly $K$ buttons ($1 \leq K \leq 1,000$), what is the maximum number of points she can earn?

Input

• Line $1$: Two space-separated integers: $N$ and $K$.
• Lines $2\cdots N+1$: Line $i+1$ contains only the string $S_i$, representing combo $i$.

Output

• Line $1$: A single integer, the maximum number of points Bessie can obtain.

Samples

3 7
ABA
CB
ABACB

4

Note

The optimal sequence of buttons in this case is ABACBCB, which gives $4$ points--$1$ from ABA, $1$ from ABACB, and $2$ from CB.

Resources

USACO Jan 2012