配点 : $300$ 点

問題文

英小文字のみからなる $N$ 個の文字列 $S_1,S_2,\dots,S_N$ が与えられます。

$S_1,S_2,\dots,S_N$ から文字列を好きな個数選ぶことを考えます。

このとき、「選んだ文字列の中でちょうど $K$ 個の文字列に登場する英小文字」の種類数としてあり得る最大値を求めてください。

制約

• $1 \le N \le 15$
• $1 \le K \le N$
• $N,K$ は整数
• $S_i$ は英小文字からなる空でない文字列である。
• $1 \le i \le N$ を満たす整数 $i$ に対し、$S_i$ に同じ文字は $2$ 個以上含まれない。
• $i \neq j$ ならば $S_i \neq S_j$ である。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$

$S_1$

$S_2$

$\vdots$

$S_N$

出力

答えを出力せよ。

4 2
abi
aef
bc
acg

3

$S_1,S_3,S_4$ を選んだ場合、a,b,c がちょうど $2$ 個の文字列に含まれます。

$4$ 個以上の文字がちょうど $2$ 個の文字列に含まれるような選び方は存在しないため、答えは $3$ です。

2 2
a
b

0

同じ文字列を複数回選ぶことはできません。

5 2
abpqxyz
az
pq
bc
cy

7