Parity

You are given $n$ binary strings $s_1, \dots, s_n$, all of the same length $m$. Each string $s_i$ comes with a bit $b_i$. The strings are $0$-indexed.

For a subset $S \subseteq \{0, 1, \dots, m-1\}$ of column indices, define the value it produces on string $s_i$ as the XOR of the bits of $s_i$ at the positions in $S$. (The XOR of a set of bits is $1$ if an odd number of them are $1$, and $0$ otherwise; the XOR of the empty set is $0$.)

You are given a nonnegative integer $k$. You want to choose a subset $S$ of size at most $k$ so that for every $i = 1, \dots, n$, the value produced on $s_i$ equals $b_i$.

For example, if $s_1 = 1010$ and $S = \{0, 3\}$, then the value on $s_1$ is $1$ (the bit at index $0$) XOR $0$ (the bit at index $3$), which is $1$.

Among all valid subsets $S$ of size at most $k$, output the minimum possible size. If no such subset exists, report that instead.

The first line contains two space-separated integers $n$ and $k$ ($1 \le n \le 64$, $0 \le k \le 10$).

Each of the next $n$ lines contains a string $s_i$, a single space, and its bit $b_i$. All strings have the same length $m$ ($1 \le m \le 50$), and $k \le m$.

Output a single integer: the minimum possible size of a subset $S \subseteq \{0, 1, \dots, m-1\}$ with $|S| \le k$ such that the XOR of the bits of $s_i$ over the indices in $S$ equals $b_i$ for every $i$. If no such subset exists, output $-1$.