Score : $900$ points

Problem Statement

For a set $X$ of non-negative integers, let $f(X)$ denote the set of non-negative integers that can be represented as the bitwise $\mathrm{XOR}$ of two integers (possibly the same) in $X$. As an example, for $X=\lbrace 1, 2, 4\rbrace$, we have $f(X)=\lbrace 0, 3, 5, 6\rbrace$.

You are given a set of $N$ non-negative integers less than $2^M$: $S=\lbrace A_1, A_2, \dots, A_N\rbrace$.

You may perform the following operation any number of times.

• Divide $S$ into two sets $T_1$ and $T_2$ (one of them may be empty). Then, replace $S$ with the union of $f(T_1)$ and $f(T_2)$.

Find the minimum number of operations needed to make $S=\lbrace 0\rbrace$.

Constraints

• $1 \leq N \leq 300$
• $1 \leq M \leq 300$
• $0 \leq A_i < 2^{M}$
• $A_i\ (1\leq i \leq N)$ are pairwise distinct.
• Each $A_i$ is given with exactly $M$ digits in binary (possibly with leading zeros).
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$

$A_1$

$A_2$

$\vdots$

$A_N$

Output

Print the answer.

4 2
00
01
10
11

2

In the first operation, you can divide $S$ into $T_1=\lbrace 0, 1\rbrace, T_2=\lbrace 2, 3\rbrace$, for which $f(T_1) =\lbrace 0, 1\rbrace, f(T_2) =\lbrace 0, 1\rbrace$, replacing $S$ with $\lbrace 0, 1\rbrace$.

In the second operation, you can divide $S$ into $T_1=\lbrace 0\rbrace, T_2=\lbrace 1\rbrace$, making $S=\lbrace 0\rbrace$.

There is no way to make $S=\lbrace 0\rbrace$ in fewer than two operations, so the answer is $2$.

1 8
10011011

1

In the first operation, you can divide $S$ into $T_1=\lbrace 155\rbrace, T_2=\lbrace \rbrace$, making $S=\lbrace 0\rbrace$. Note that $T_1$ or $T_2$ may be empty.

1 2
00

0

We have $S=\lbrace 0\rbrace$ from the beginning; no operation is needed.

20 20
10011011111101101111
10100111100001111100
10100111100110001111
10011011100011011111
11001000001110011010
10100111111011000101
11110100001001110010
10011011100010111001
11110100001000011010
01010011101011010011
11110100010000111100
01010011101101101111
10011011100010110111
01101111101110001110
00111100000101111010
01010011101111010100
10011011100010110100
01010011110010010011
10100111111111000001
10100111111000010101

10