103582: [Atcoder]ABC358 C - Popcorn

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

问题描述

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

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

Takahashi想尝试所有口味的爆米花，但不想走太远。确定Takahashi需要访问的最少摊位数，以便购买所有口味的爆米花。

限制条件

• $N$和$M$是整数。
• $1 \leq N, M \leq 10$
• 每个$S_i$是由o和x组成的长度为$M$的字符串。
• 对于每个$i$ $(1 \leq i \leq N)$，$S_i$中至少有一个o。
• 对于每个$j$ $(1 \leq j \leq M)$，存在至少一个$i$使得$S_i$的第$j$个字符是o。

输入

输入通过标准输入给出以下格式：

$N$ $M$
$S_1$
$S_2$
$\vdots$
$S_N$

输出

打印Takahashi购买所有口味爆米花所需的最少摊位数。

样例输入1

3 5
oooxx
xooox
xxooo

样例输出1

2

通过访问第1个和第3个摊位，你可以购买所有口味的爆米花。不可能从一个摊位购买所有口味，所以答案是$2$。

样例输入2

3 2
oo
ox
xo

样例输出2

1

样例输入3

8 6
xxoxxo
xxoxxx
xoxxxx
xxxoxx
xxoooo
xxxxox
xoxxox
oxoxxo

样例输出3

3