C - 天下一文字列集合

Time Limit: 5 sec / Memory Limit: 256 MB

問題文

英小文字 (az) と、英小文字 1 文字と一致するワイルドカード (*) からなる m 文字の文字列のパターンが n 個与えられる。
この文字列のパターンは、 m 文字の英小文字からなる文字列の集合 X のいずれかの要素に一致するようにように作られたものである。

集合 X の要素数の最小値を求めよ、ダイキ君。


入力

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


n m
P1
P2
:
Pn

1 行目に文字列のパターンの数を表す整数 n( 1 ≦ n ≦ 14 ) と文字列の長さを表す整数 m( 1 ≦ m ≦ 100000 ) が与えられる。 その後、長さ m の文字列のパターン P_in 行で与えられる。

部分点

  • 1 ≦ n ≦ 4, 1 ≦ m ≦ 4 の全てのテストケースに正解した場合、部分点として20点が与えられる
  • 1 ≦ n ≦ 14, 1 ≦ m ≦ 10 の全てのテストケースに正解した場合、部分点としてさらに30点が与えられる

出力

集合 X としてありうる要素数のうち最小の値を1行で出力せよ。 なお、行の終端には改行が必要である。

入力例1

5 4
a*x*
*xx*
*x*b
**cb
****

出力例1

2

集合 X の例としては、

axxb
oocb

がありうる。


Source Name

天下一プログラマーコンテスト2014 予選A