You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题重述

在游乐园中存在 ( N ) 个爆米花摊位，其编号范围是从 ( 1 ) 到 ( N ) 。爆米花拥有 ( M ) 种不同的口味，编号从 ( 1 ) 到 ( M ) 。每个摊位所售卖的口味信息通过一个长度为 ( M ) 的字符串来呈现：当字符串中的字符为 o 时，表示该摊位售卖对应的口味；当字符为 x 时，则表示不售卖该口味。并且每个摊位至少会售卖一种口味的爆米花，同时每种口味的爆米花至少在一个摊位有售卖。

小Z想要购买到所有 ( M ) 种口味的爆米花，然而希望尽可能减少访问摊位的数量。现在需要求出最少要访问多少个摊位，才能够买到所有口味的爆米花。

输入格式

1. 第一行：包含两个整数 ( N ) 和 ( M ) ，分别代表爆米花摊位的数量和爆米花口味的种类数。
2. 接下来的 ( N ) 行：每行都是一个长度为 ( M ) 的字符串 ( S_i ) ，该字符串表示摊位 ( i ) 所售卖的口味信息。

输出格式

输出一个整数，代表最少需要访问的摊位数量。

示例分析

示例 1

输入：

3 5
oooxx
xooox
xxooo

输出：

2

解释：

• 摊位 1 售卖口味 1, 2, 3, 4（这里假设口味编号从 1 开始计数）。
• 摊位 2 售卖口味 2, 3, 4, 5。
• 摊位 3 售卖口味 3, 4, 5。
• 经过分析可知，最少需要访问摊位 1 和摊位 3 ，便可以覆盖到所有的口味（即 1, 2, 3, 4, 5 这 5 种口味）。

示例 2

输入：

3 2
oo
ox
xo

输出：

1

解释：

• 摊位 1 售卖口味 1 和 2。
• 摊位 2 售卖口味 1 和 2。
• 摊位 3 售卖口味 1 和 2。
• 由于每个摊位都能覆盖到所有的口味，所以任意选择一个摊位即可，因此最少需要访问 1 个摊位。

示例 3

输入：

8 6
xxoxxo
xxoxxx
xoxxxx
xxxoxx
xxoooo
xxxxox
xoxxox
oxoxxo

输出：

3

解释：

• 在这种情况下，经过合理的选择，需要选择至少 3 个摊位才能够覆盖到所有的 6 种口味。