問題文

chinerist 君はインデント幅を1にしてコーディングしていた罪で yuki 刑務所に投獄されてしまいました。

yuki 刑務所には $N$ 人の看守 $i(1\le i\le N)$ がいて、各看守は $M$ 種類の鍵 $j(1\le j\le M)$ のうちいくつかを所持しています。 看守 $i$ が各鍵を所持しているかについては o,x のみからなる長さ $M$ の文字列 $S_i=S_{i1}{S}_{i2}\dots S_{iM}$ で表され、 $S_{ij}=$o のとき看守 $i$ が鍵 $j$ を所持していることを、$S_{ij}=$x のとき看守 $i$ が鍵 $j$ を所持していないことを表します。 各鍵 $j(1\le j\le M)$ は $1$ 人以上の看守が所持しています。

yuki 刑務所から脱獄するには $M$ 種類の鍵がそれぞれ $1$ つ以上必要です。 chinerist 君は何人かの看守を襲って、それぞれが所持している鍵をすべて強奪することで鍵を集めることにしました。

以下の条件を満たす最小の整数 $K$ を求めてください。

• $N$ 人の看守のうちどの $K$ 人を襲っても、$M$ 種類の鍵をそれぞれ $1$ つ以上手に入れることができる

入力

$N$ $M$
$S_1$
$S_2$
$⋮$
$S_N$

• $1\le N\le 1000$
• $1\le M\le 1000$
• $S_i$ はo、x のみからなる長さ $M$ の文字列
• 各 $j(1\le j\le M)$ に対し、 $S_{ij}=$o を満たす $i$ が1つ以上存在する

出力

答えを出力してください。

最後に改行してください。

サンプル

3 3
oxo
xoo
oox

2

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

8