题目描述

在乔斯乐园里，有 N 个爆米花摊位，编号从 1 到 N。它们有 M 种不同口味的爆米花，标号为 1, 2, ⋯, M，但并不是每个摊位都出售所有口味的爆米花。

强哥获得了关于每个摊位销售哪种口味爆米花的信息。这些信息由长度为 M 的 N 个字符串。如果 $k_{i,j}$ 的字符是 o，则表示第 i 个摊位出售第 j 种口味的爆米花。如果是 x，则表示第 i 个摊位不出售第 j 种口味的爆米花。

每个摊位至少出售一种口味的爆米花，每种口味的爆米花至少在一个摊位出售。

强哥想尝遍所有口味的爆米花，但又不想走动太多。求强哥至少要去多少个摊位才能买到所有口味的爆米花？

• $1≤N,M≤10$

输入格式

第一行包含两个整数，$N,M$

接下来 $N$行 $M$列 的二维字符数组。

输出格式

强哥最少要去的摊位数量，才能买到所有口味的爆米花。

3 5
oooxx
xooox
xxooo

2

8 6
xxoxxo
xxoxxx
xoxxxx
xxxoxx
xxoooo
xxxxox
xoxxox
oxoxxo

3

提示