[ABC358] C - Popcorn

C - Popcorn

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 300 分

题面

在 AtCoder Land，有 个编号为 到 的爆米花摊位。它们有 种不同口味的爆米花，标记为 ，但并非每个摊位都销售所有口味的爆米花。

小高得知了每个摊位销售哪些口味的爆米花的信息。这些信息用 个长度为 的字符串 表示。如果 的第 个字符是 o，表示摊位 销售口味为 的爆米花。如果是 x，表示摊位 不销售口味为 的爆米花。每个摊位至少销售一种口味的爆米花，每种口味的爆米花至少在一个摊位销售。

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

限制条件

• 和 是整数。
• 每个 是一个长度为 的字符串，由 o 和 x 组成。
• 对于每个 ， 中至少有一个 o。
• 对于每个 ，至少有一个 ，使得 的第 个字符为 o。

---

输入

输入从标准输入中获得，格式如下：

输出

打印小高所需访问的摊位的最小数量，以购买所有口味的爆米花。

---

输入样例 1

3 5
oooxx
xooox
xxooo

输出样例 1

2

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

---

输入样例 2

3 2
oo
ox
xo

输出样例 2

1

---

输入样例 3

8 6
xxoxxo
xxoxxx
xoxxxx
xxxoxx
xxoooo
xxxxox
xoxxox
oxoxxo

输出样例 3

3