패리티

길이가 모두 $m$으로 같은 $n$개의 이진 문자열 $s_1, \dots, s_n$이 주어진다. 각 문자열 $s_i$에는 비트 $b_i$가 하나씩 함께 주어진다. 문자열의 인덱스는 $0$부터 시작한다.

열 인덱스의 부분집합 $S \subseteq \{0, 1, \dots, m-1\}$에 대해, 이 집합이 문자열 $s_i$에 대해 만들어 내는 값을 "$S$에 속한 위치들에서의 $s_i$ 비트들의 XOR"로 정의한다. (비트들의 XOR은 값이 $1$인 비트의 개수가 홀수이면 $1$, 아니면 $0$이다. 공집합의 XOR은 $0$이다.)

음이 아닌 정수 $k$가 주어진다. 모든 $i = 1, \dots, n$에 대해 $s_i$에 대해 만들어지는 값이 $b_i$와 같도록, 크기가 $k$ 이하인 부분집합 $S$를 고르고자 한다.

예를 들어 $s_1 = 1010$이고 $S = \{0, 3\}$이면, $s_1$에 대한 값은 인덱스 $0$의 비트 $1$과 인덱스 $3$의 비트 $0$의 XOR인 $1$이다.

크기가 $k$ 이하인 모든 유효한 부분집합 $S$ 중에서, 가능한 최소 크기를 출력한다. 그러한 부분집합이 존재하지 않으면 대신 그 사실을 알린다.

첫째 줄에 두 정수 $n$과 $k$가 공백으로 구분되어 주어진다 ($1 \le n \le 64$, $0 \le k \le 10$).

이어지는 $n$개의 줄 각각에는 문자열 $s_i$, 공백 하나, 그리고 비트 $b_i$가 주어진다. 모든 문자열의 길이는 $m$으로 같으며 ($1 \le m \le 50$), $k \le m$이다.

$|S| \le k$이면서 모든 $i$에 대해 $S$에 속한 인덱스들에서의 $s_i$ 비트들의 XOR가 $b_i$와 같은 부분집합 $S \subseteq \{0, 1, \dots, m-1\}$의 최소 크기를 정수 하나로 출력한다. 그러한 부분집합이 존재하지 않으면 $-1$을 출력한다.