题目描述

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 \le N \le 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 \le K \le 1,000$ ), what is the maximum number of points she can earn?

题意简述:给出 $n$ 个 $ABC$ 串$combo[1..n]$ 和 $k$ ，现要求生成一个长 $k$ 的字符串 $S$，问 $S$ 与 $word[1..n]$ 的最大匹配数

输入格式

Line $1$ : Two space-separated integers: $N$ and $K$ .

Lines $2..N+1$ : Line $i+1$ contains only the string $S_i$ , representing combo $i$ .

输出格式

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

3 7 ABA CB ABACB

4

提示

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