配点 : $200$ 点

問題文

A社のあるプロジェクトチームにはリーダーと社員 $1, 2, \\ldots , N$ の合計 $N+1$ 人が属しています。

$D$ 日間のうち、リーダーは毎日出勤します。$1, 2, \\ldots , D$ 日目についての、リーダー以外の各社員の出勤予定はそれぞれ長さ $N$ の文字列 $S_1, S_2, \\ldots , S_D$ で与えられます。$i$ 日目に社員 $j$ ($1 \\leq j \\leq N$) が出勤する場合 $S_i$ の $j$ 文字目は o であり、出勤しない場合 x です。

リーダーは、ある重要事項を他の社員たちに伝達するため、$D$ 日間のうち $2$ 日を選んで会議を行おうとしています。

各社員は、その社員の出社日のみ会議に参加することができます。

重要事項ははじめリーダーのみが知っており、他の社員は会議に参加すると知ることができます。

リーダー以外の $N$ 人のうち、最大で何人の社員に重要事項を伝達できるか求めてください。

制約

• $1 \\leq N \\leq 10$
• $2 \\leq D \\leq 10$
• $N, D$ は整数である。
• $S_i$ は長さ $N$ の文字列である。
• $S_i$ の各文字は o または x である。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $D$ $S_1$ $S_2$ : $S_D$

出力

$D$ 日間のうち $2$ 日選んで会議を行ったとき、リーダー以外の $N$ 人のうち最大何人の社員に重要事項を伝達できるかを、$1$ 行に出力せよ。

入力例 1

2 3
xx
ox
oo

出力例 1

2

$2$ 日目にリーダーと社員 $1$ で会議を行うと、社員 $1$ が重要事項を知ります。

次に $3$ 日目にリーダーと社員 $1, 2$ で会議を行うと、社員 $2$ が重要事項を知ります。

入力例 2

3 3
xox
oxx
xxo

出力例 2

2

$2$ 日目にリーダーと社員 $1$ で会議を行うと、社員 $1$ が重要事項を知ります。

次に $3$ 日目にリーダーと社員 $3$ で会議を行うと、社員 $3$ が重要事項を知ります。

全員が重要事項を知っている状態にすることは不可能なので、$2$ と出力します。

入力例 3

5 4
oxxox
xoxxx
xxoxo
oxxxo

出力例 3

4