앙상블할래?

서울사이버대학교 인공지능학과 개설을 기념하여, 노교수와 천교수는 학생들에게 이진 분류 인공지능 모델을 각자 하나씩 개발해 오라는 과제를 냈다. 개발된 모델들의 성능을 평가하던 두 교수는 모델들을 결합한 앙상블로 성능을 높일 수 있는지 궁금해졌다. 앙상블은 여러 모델의 결과를 조합하는 방법이다. 이번에는 각 예측 항목마다 더 많은 모델이 출력한 값을 최종 결과로 채택하는 하드 보팅 앙상블을 써 보기로 했다. 이 문제에서는 앙상블할 때 홀수 개의 모델만 선택한다고 가정한다.

예를 들어, 6개의 예측 항목에 대한 정답이 $[0, 1, 0, 1, 1, 0]$이고, 네 학생의 모델 예측 결과가 아래와 같이 주어진다고 하자.

• 1번 학생: $[1, 0, 0, 1, 1, 0]$
• 2번 학생: $[0, 1, 1, 1, 1, 0]$
• 3번 학생: $[0, 1, 0, 0, 0, 0]$
• 4번 학생: $[0, 0, 1, 0, 1, 0]$

1번, 2번, 4번 학생의 모델을 선택해 하드 보팅으로 앙상블하면 결과는 $[0, 0, 1, 1, 1, 0]$이다. 항목별로 보면 다음과 같다.

• 첫 번째 항목: 0이 두 번, 1이 한 번 나와 최종 예측은 0
• 두 번째 항목: 0이 두 번, 1이 한 번 나와 최종 예측은 0
• 세 번째 항목: 0이 한 번, 1이 두 번 나와 최종 예측은 1
• 네 번째 항목: 0이 한 번, 1이 두 번 나와 최종 예측은 1
• 다섯 번째 항목: 0은 없고 1이 세 번 나와 최종 예측은 1
• 여섯 번째 항목: 0이 세 번, 1은 없어 최종 예측은 0

이 앙상블 결과를 정답과 비교하면 6개 항목 중 4개가 일치하므로 정확도는 $\frac{4}{6}$이다.

정확도가 가장 뛰어난 모델 하나만 선택했을 때보다 더 높은 정확도를 가지는 앙상블 조합이 존재하면, 앙상블로 성능을 향상시킬 수 있다고 판단한다. 그러한 조합이 있는지 확인하라.

첫 번째 줄에 모델의 수 $N$와 예측 항목의 수 $M$이 주어진다. $(1 \le N \le 16;$ $1 \le M \le 100)$

두 번째 줄에 $M$개의 각 예측 항목에 대한 정답이 순서대로 주어진다.

세 번째 줄부터 $N$개의 줄에 걸쳐 각 모델의 예측 결과 $M$개가 순서대로 주어진다.

정답과 예측 결과는 모두 $0$ 또는 $1$로만 구성되며, 공백으로 구분되어 주어진다.

첫 번째 줄에 하드 보팅 앙상블로 가장 정확도가 높은 단일 모델의 정확도를 뛰어넘는 조합이 있다면 1을, 그렇지 않다면 0을 출력한다.