패리티

시간 제한10초메모리 제한512 MB

요약

이진 문자열 n개와 각각의 목표 비트가 주어질 때, 각 문자열에서 선택한 열들의 XOR이 목표 비트와 같아지는 크기 k 이하의 최소 열 부분집합을 구한다.

난이도: 보통10점 중 7점
유형: 비트 연산, 그리디, 완전 탐색, 수학
정답자: 아직 제출이 없습니다

문제

길이가 모두 $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$ 을 출력한다.

예제5

예제 1
입력
```
3 1
111 1
001 0
011 1
```
예상 출력
```
1
```

예제 2

입력

4 7
010001000111100011010010000011110000000000 0
001101010101000101001011110001101010101111 0
100111100101100000110000110110010110100101 0
011010001110101111000000111101100010111111 1

예상 출력

예제 3
입력
```
2 3
10 0
01 0
```
예상 출력
```
0
```
예제 4
입력
```
2 2
10 1
01 1
```
예상 출력
```
2
```
예제 5
입력
```
2 0
10 1
01 0
```
예상 출력
```
-1
```