Problem Description

In a certain project team at Company A, there are a leader and employees $1, 2, \ldots, N$, totaling $N+1$ people.

For $D$ days, the leader will attend work every day. The attendance schedule for each employee (excluding the leader) for each day from $1, 2, \ldots, D$ is given as a string of length $N$, denoted as $S_1, S_2, \ldots, S_D$. If employee $j$ ($1 \leq j \leq N$) attends work on day $i$, the $j$-th character of $S_i$ is o; otherwise, it is x.

The leader wants to convey an important matter to the other employees by holding meetings on two chosen days out of the $D$ days.

Each employee can only attend the meeting on their workdays.

The important matter is initially known only to the leader, and other employees can learn it when they attend a meeting.

Among the $N$ employees (excluding the leader), determine the maximum number of employees who can be informed about the important matter.

Input Format

The input is given from the standard input in the following format:

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

Output Format

Output a single line indicating the maximum number of employees (excluding the leader) who can be informed about the important matter when meetings are held on two chosen days out of the $D$ days.

Sample Input and Output

Sample Input #1

2 3
xx
ox
oo

Sample Output #1

2

Sample Input #2

3 3
xox
oxx
xxo

Sample Output #2

2

Sample Input #3

5 4
oxxox
xoxxx
xxoxo
oxxxo

Sample Output #3

4

Notes/Hints

Constraints

• $1 \leq N \leq 10$
• $2 \leq D \leq 10$
• $N, D$ are integers.
• $S_i$ is a string of length $N$.
• Each character in $S_i$ is either o or x.

Sample Explanation 1

If a meeting is held on day 2 with the leader and employee 1, employee 1 will learn the important matter. Then, if a meeting is held on day 3 with the leader and employees 1, 2, employee 2 will learn the important matter.

Sample Explanation 2

If a meeting is held on day 2 with the leader and employee 1, employee 1 will learn the important matter. Then, if a meeting is held on day 3 with the leader and employee 3, employee 3 will learn the important matter. It is impossible to have all employees know the important matter, so the output is 2.

见题面 Input 部分

见题面 Output 部分