← 返回题目列表

AtCoder · abc358_c

F. 爆米花

中文机器翻译题面 查看原题

分数: 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),至少有一个 o in 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