分数: 300 点
问题陈述
在AtCoder Land,有 N 爆米花摊编号 1 to N。他们有 M 不同口味的爆米花,贴上标签 1, 2, \dots, M,但并非每个摊位都出售所有口味的爆米花。
高桥已获得有关每个摊位出售哪些口味的爆米花的信息。该信息表示为 N 字符串 S_1, S_2, \dots, S_N 长度 M。如果 j- 第一个字符 S_i is o,表示站立 i 卖味道 j 爆米花。如果是的话 x,表示站立 i 不卖香精 j。每个摊位至少出售一种口味的爆米花,并且每种口味的爆米花至少在一个摊位出售。
高桥想尝试所有口味的爆米花,但又不想走动太多。确定高桥购买所有口味的爆米花需要访问的最少摊位数量。
约束
- N 和 M 是整数。
- 1 \leq N, M \leq 10
- 每个 S_i 是一个长度为的字符串 M 组成
o和x. - 对于每个 i (1 \leq i \leq N),至少有一个
oin S_i. - 对于每个 j (1 \leq j \leq M),至少有一个 i 这样 j- 第一个字符 S_i is
o.
输入
输入由标准输入按以下格式给出:
N M S_1 S_2 \vdots S_N
输出
打印高桥购买所有口味爆米花需要访问的最少摊位数量。
示例输入 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