Score : $300$ points

问题陈述

在AtCoder Land，有$N$个爆米花摊位，编号从$1$到$N$。它们有$M$种不同的爆米花口味，标记为$1, 2, \dots, M$，但并不是每个摊位都出售所有口味的爆米花。

高桥获得了关于每个摊位出售哪些口味爆米花的信息。这些信息由$N$个长度为$M$的字符串$S_1, S_2, \dots, S_N$表示。如果$S_i$的第$j$个字符是o，这意味着摊位$i$出售第$j$种口味的爆米花。如果是x，则意味着摊位$i$不出售第$j$种口味的爆米花。每个摊位至少出售一种口味的爆米花，每种口味的爆米花至少在一个摊位出售。

高桥想要尝试所有口味的爆米花，但不想走太多路。确定高桥需要访问的最少摊位数量，以购买所有口味的爆米花。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

In AtCoder Land, there are $N$ popcorn stands numbered $1$ to $N$. They have $M$ different flavors of popcorn, labeled $1, 2, \dots, M$, but not every stand sells all flavors of popcorn.

Takahashi has obtained information about which flavors of popcorn are sold at each stand. This information is represented by $N$ strings $S_1, S_2, \dots, S_N$ of length $M$. If the $j$-th character of $S_i$ is o, it means that stand $i$ sells flavor $j$ of popcorn. If it is x, it means that stand $i$ does not sell flavor $j$. Each stand sells at least one flavor of popcorn, and each flavor of popcorn is sold at least at one stand.

Takahashi wants to try all the flavors of popcorn but does not want to move around too much. Determine the minimum number of stands Takahashi needs to visit to buy all the flavors of popcorn.

Constraints

• $N$ and $M$ are integers.
• $1 \leq N, M \leq 10$
• Each $S_i$ is a string of length $M$ consisting of o and x.
• For every $i$ $(1 \leq i \leq N)$, there is at least one o in $S_i$.
• For every $j$ $(1 \leq j \leq M)$, there is at least one $i$ such that the $j$-th character of $S_i$ is o.

Input

The input is given from Standard Input in the following format:

$N$ $M$

$S_1$

$S_2$

$\vdots$

$S_N$

Output

Print the minimum number of stands Takahashi needs to visit to buy all the flavors of popcorn.

Sample Input 1

3 5
oooxx
xooox
xxooo

Sample Output 1

2

By visiting the 1st and 3rd stands, you can buy all the flavors of popcorn. It is impossible to buy all the flavors from a single stand, so the answer is $2$.

Sample Input 2

3 2
oo
ox
xo

Sample Output 2

1

Sample Input 3

8 6
xxoxxo
xxoxxx
xoxxxx
xxxoxx
xxoooo
xxxxox
xoxxox
oxoxxo

Sample Output 3

3