#y0008. 字符串匹配

字符串匹配

题目描述

给出 nn 个字符串长度为 mm,且由 0,1,* 组成的字符串集合 SS,且每个字符串中 * 最多出现一次,定义字符串 ss 能匹配 01 串 tt 仅当 lens=lentlen_s=len_t 且 si=ti or si=∗s_i=t_i \ \text{or} \ s_i=*,其中 lenlen 为字符串的长度。

你需要构造字符串长度为 mm,且由 0,1,* 组成的字符串集合 S′S',且每个字符串中 * 最多出现一次,使得 SS 可以匹配的 01 串集合与 S′S' 可以匹配的 01 串集合相等。请输出 S′S' 的最短长度。

输入格式

第一行两个正整数 n,mn,m。

接下来的 nn 行,每行一个长度为 mm 的字符串 SiS_i。

输出格式

输出一行一个整数,表示 S′S' 的最短长度。

输入输出样例

输入

3 3
*01
100
011

输出

2

样例解释

所构造出的 S′={0 ⁣∗ ⁣1,10∗}S'=\{0\!*\!1,10*\}。

它们都能匹配 {001,101,100,011}\{001,101,100,011\}。

数据范围

1≤n≤1000,1≤m≤101\le n\le 1000,1\le m\le 10。