爆米花

题目描述

在 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$。每个摊至少售卖一种口味的爆米花，且每种口味的爆米花至少有一个摊售卖。

高桥想尝遍所有口味的爆米花，但不想走太多路。求为了买到所有口味的爆米花，高桥最少需要访问多少个摊。

输入格式

输入按以下格式从标准输入给出：

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

输出格式

输出为了买到所有口味的爆米花，高桥最少需要访问的摊的数量。

样例

3 5
oooxx
xooox
xxooo

2

访问第 $1$ 个和第 $3$ 个摊就能买到所有口味的爆米花。只访问一个摊不可能买到所有口味，因此答案为 $2$。

3 2
oo
ox
xo

1

8 6
xxoxxo
xxoxxx
xoxxxx
xxxoxx
xxoooo
xxxxox
xoxxox
oxoxxo

3

数据范围

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