RoAlgo Contest #12 - NiceContest | F. Nice Scam

Baiatu' Bombonel has just finished setting up the Scam School curriculum. The first lesson included in the Scam School curriculum is that to be a successful scammer, you must know how not to get scammed. To teach this introductory lesson, Baiatu' Bombonel has promised to place as many students who are friends with each other in a classroom. But, being an expert scammer, Baiatu' Bombonel wants to scam them to the maximum; he wants to place as many students in a classroom who do not know each other. The IDs of each of the $N$ students are known, represented by a binary string of length $M$ each, and it is known that students $i$ and $j$ are friends only if their IDs differ by exactly one bit.

Task

Given $N$, $M$ and the $N$ IDs of the students, determine the maximum number of students Baiatu' Bombonel can place in a classroom, under the condition that none of them know any other student in the classroom.

Input data

The first line will contain the numbers $N$ and $M$, representing the number of students and the length of the IDs, respectively. Each of the next $N$ lines will contain a binary string of length $M$, representing the IDs of the students.

Output data

Print the maximum number of students Baiatu' Bombonel can place in a classroom, with the condition that none of them know any other student in the classroom.

Constraints and clarifications

• $1 \leq N, M \leq 1\ 000$;
• For tests worth $10$ points, $N \leq 17, M \leq 10$;
• For other tests worth $10$ points, $N \leq 17, M \leq 1\ 000$;
• For other tests worth $30$ points, $N \leq 1\ 000, M \leq 30$;
• Each of the $N$ students have distinct IDs.

Example 1

stdin

4 4
0000
1100
0011
1111

stdout

4

Explanation

Baiatu' Bombonel can put all of the students in the same classroom, since none are friends with each other.

Example 2

stdin

4 4
0000
1100
0011
1000

stdout

3

Explanation

We can choose students $0$, $1$ and $2$ and leave $3$ out.