题目描述

贝西正在玩电子游戏！在游戏中，三个字母"$\red{A}$"、"$\red{B}$"和"$\red{C}$"是唯一有效的按钮。$\red{Bessie }$可以按她喜欢的任何顺序按下按钮；但是，只有 $\red{N }$个不同的组合可能（$\red{1 <= N <= 20}$）。

组合 $\red{i }$表示为长度在 $\red{1 }$到 $\red{15 }$之间的字符串 $\red{S_i，}$并且仅包含字母"$\red{A}$"、"$\red{B}$"和"$\red{C}$"。每当 $\red{Bessie }$按下与组合匹配的字母组合时，她就会为该组合获得一分。组合可能会相互重叠，甚至同时完成！

例如，如果 $\red{N = 3 }$并且三个可能的组合是"$\red{ABA}$"、"$\red{CB}$"和"$\red{ABACB}$"，并且 $\red{Bessie }$按"$\red{ABACB}$"，她将以 $\red{3 }$分结束。$\red{Bessie }$可能不止一次为一个组合得分。贝西当然希望眷获得积分。

如果她正好按了 $\red{K }$个按钮（$\red{1 <= K <= 1,000}$），她最多可以获得多少分？

提出一个$\red{ABC}$串$\red{combo[1..n]}$和$\red{k，}$现生成一个长$\red{k}$的字符串$\red{S，}$问$\red{S}$与$\red{word[1..n]}$的最大匹配数

输入格式

第 $\red{1 }$行：两个空格分隔的整数：$\red{N }$和 $\red{K}$。

第 $\red{2..N+1 }$行：第 $\red{i+1 }$行仅包含字符串 $\red{S_i，}$表示组合 $\red{i}$。

输出格式

第 $\red{1 }$行：单个整数，$\red{Bessie }$可以获得的最大点数。

样例

输入样例

3 7 ABA CB ABACB

输出样例

4

提示

在这种情况下，按钮的最佳顺序是 $\red{ABACBCB，}$它给出 $\red{4 }$分——$\red{ABA }$获得 $\red{1 }$分，$\red{ABACB }$获得 $\red{1 }$分，$\red{CB }$获得 $\red{2 }$分。