题目描述

给出 $n$ 个字符串长度为 $m$，且由 0，1，* 组成的字符串集合 $S$，且每个字符串中 * 最多出现一次，定义字符串 $s$ 能匹配 01 串 $t$ 仅当 $len_s=len_t$ 且 $s_i=t_i \ \text{or} \ s_i=*$，其中 $len$ 为字符串的长度。

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

输入格式

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

接下来的 $n$ 行，每行一个长度为 $m$ 的字符串 $S_i$。

输出格式

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

输入输出样例

输入

3 3
*01
100
011

输出

2

样例解释

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

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

数据范围

$1\le n\le 1000,1\le m\le 10$。