10878번 - How many binary sequences? 다국어

문제

You are given a set of N integer sequences Z = {Z₁, Z₂, ··· , Z_N}, where |Z_i| = K for i = 1, 2, ··· , N.

The N integer sequences in the set were generated by the following generation process:

1. For i-th generation, select a binary integer sequence X ∈ B arbitrary, where B is a set of binary sequences of length K. Let’s denote X = {x₁, x₂, ··· , x_K} where x_j ∈ {0, 1} for j = 1, 2, ··· , K.
2. Select a binary integer sequence Y ∈ B arbitrary so that dist(X, Y) ≤ 2. Here dist(X, Y) denotes the hamming distance between X and Y , which is the distance measure between two sequences of equal length is the number of positions at which the corresponding digits are different. For example, dist({1, 0, 1, 1}, {1, 1, 1, 1}) is 1 and dist({1, 0, 1, 1, 1, 0, 1}, {1, 0, 0, 1, 0, 0, 1}) is 2.
3. As the final result, we can generate an integer sequence Z_i, by given X and Y. Z_i is the i-th generated integer sequence defined by Z_i = {x₁ + y₁, x₂ + y₂, · · · , x_K + y_K}.

For example, an integer sequence Z_i = {1, 0, 1, 2, 2} can be generated by two binary sequences X = {1, 0, 0, 1, 1} and Y = {0, 0, 1, 1, 1}.

Given N integer sequences generated, write a program to find how many elements in the set B. If there are several possible solutions, find the one with minimum set size.

입력

The first line of the input contains two integers K and N (1 ≤ K ≤ 20, 1 ≤ N ≤ 24). A whitespace character separates those two numbers. Each of the following N lines contains elements of Z. The jth number in the i-th line represents Z_i,j, the value of the j-th element of Z_i. There are no delimiter characters between adjacent numbers in these N lines.

출력

Print the minimum number of elements in the set B.

제한

힌트

In the sample, we can generate each element in the set Z by letting X = {1, 0, 0, 1, 1}, Y = {0, 0, 1, 1, 1} and X = {1, 0, 0, 1, 1}, Y = {1, 0, 0, 1, 1}, respectively. Therefore, Z can be constructed by the set B = {{1, 0, 0, 1, 1} and {0, 0, 1, 1, 1}}.