← 返回题目列表

AtCoder · tenka1_2014_qualA_c

C. 天下一字符串集

中文机器翻译题面 查看原题

問題文

英小文字 (a~z) 和小写字母 1 与字符 (*) m 字符串的模式是 给出了 n 。
这个字符串模式是 m 由小写字母组成的字符串集合 它旨在匹配 X 的任何元素。 求

集合 X 中元素的最小数量,Daiki 先生。


入力

输入是按以下格式从标准输入给出的。


n m
P1
P2
:
Pn

1 一个整数,表示行中字符串模式的数量 n( 1 ≦ n ≦ 14 )和一个表示字符串长度的整数 给出了 m( 1 ≦ m ≦ 100000 )。 然后是长度 m 字符串模式 在 P_i 是 在 n 行中给出。

部分点

  • 1 ≦ n ≦ 4, 1 ≦ m ≦ 4 中的所有测试用例都回答正确,则将获得20分作为部分分。 如果
  • 1 ≦ n ≦ 14, 1 ≦ m ≦ 10 中的所有测试用例都回答正确,则将额外获得 30 分作为部分分。 在一行中输出

出力

集合 X 的尽可能少的元素数。 请注意,行尾需要换行。

入力例1

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

出力例1

2

集合 X 的一个例子是

axxb
oocb

是可能的。