Problem Statement

chinerist has been imprisoned in yuki Prison for the crime of coding with an indent width of 1.

In yuki Prison there are $N$ guards $i\ (1\le i \le N)$, and each guard holds some of the $M$ types of keys $j\ (1\le j \le M)$. Which keys guard $i$ holds is represented by a string $S_i=S_{i1}S_{i2}\dots S_{iM}$ of length $M$ consisting only of o,x: $S_{ij}=$o means that guard $i$ holds key $j$, and $S_{ij}=$x means that guard $i$ does not hold key $j$. Each key $j\ (1\le j \le M)$ is held by $1$ or more guards.

To escape from yuki Prison, at least $1$ of each of the $M$ types of keys is required. chinerist has decided to collect keys by assaulting some of the guards and robbing each of them of all the keys they hold.

Find the minimum integer $K$ that satisfies the following condition.

• No matter which $K$ of the $N$ guards are assaulted, at least $1$ of each of the $M$ types of keys can be obtained.

Input

$N$ $M$
$S_1$
$S_2$
$\vdots$
$S_N$

• $1 \le N \le 1000$
• $1 \le M \le 1000$
• $S_i$ is a string of length $M$ consisting only of o, x
• For each $j\ (1\le j \le M)$, there exists at least 1 $i$ such that $S_{ij}=$o

Output

Output the answer.

Print a newline at the end.

Sample

3 3
oxo
xoo
oox

2

10 15
ooxxxxooooxoxox
ooxxxooxooxxxxx
ooooooxooooxxxx
oxxoxooxoxoooxx
oxooooxoooooxoo
ooooxoxooooxxox
oxooxoxoooxxxxx
ooxoxoxoooooxoo
oooxoooxooxooxo
oxoxxoxooooxoxx

8