問題文
英小文字 (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
是可能的。