Automatic Control Machine
시간 제한2초메모리 제한1024 MB
길이 n인 이진 문자열을 최대 15개 주고, 모든 자리를 비트 OR로 덮는 최소 개수의 문자열을 고르거나 불가능하면 -1을 출력한다.
문제
회사는 Automatic Control Machine(줄여서 ACM)을 만들어 큰 인기를 얻었다. 기능이 완전하고 강력해서 회사는 여러 해 판매한 뒤 재설계를 준비하고 있다. 새 버전의 ACM도 시장에 출시되기 전에 제품의 신뢰성을 확인하기 위한 여러 검사를 거쳐야 한다. 기능이 너무 많아서 각 테스트 데이터셋은 그중 몇 개만 검출할 수 있다. 물론 모든 기능을 검사한 뒤에 제품을 출시할 수 있다. 각 검사에는 시간과 재료 비용이 들기 때문에 가능한 한 적게 검사하려고 한다. 모든 테스트 데이터셋을 실행하는 비용은 같다고 가정할 때, 모든 기능의 검사를 커버할 수 있는 테스트 데이터셋의 최소 개수를 구하라. 예를 들어 검사해야 할 기능이 5개이고, 각각 다음과 같은 기능을 커버할 수 있는 테스트 데이터셋이 6개 있다고 하자.
- 테스트 데이터셋 a: 1
- 테스트 데이터셋 b: 2, 5
- 테스트 데이터셋 c: 2, 3, 4
- 테스트 데이터셋 d: 1, 3, 5
- 테스트 데이터셋 e: 1, 3, 4
- 테스트 데이터셋 f: 3, 5
{a, b, c}도 작업을 수행할 수 있지만, {c, d}가 시간과 비용을 절약하는 면에서 더 낫다.
입력
입력 파일의 첫째 줄에는 기계의 수를 나타내는 양의 정수 T가 주어진다. 각 기계마다 첫째 줄에는 검사해야 할 기계의 기능 수와 테스트 데이터셋의 수를 나타내는 두 정수 n과 m이 주어진다. 이어서 m개의 줄이 주어지며, 각 줄에는 길이 n의 이진 문자열이 있어 해당 테스트 데이터셋이 각 기능을 검출할 수 있는지 나타낸다(1은 예, 0은 아니오).
출력
T개의 줄을 출력한다. 각 줄에는 그 기계의 모든 기능을 검사하는 데 필요한 테스트 데이터셋의 최소 개수를 출력한다. 기계의 모든 기능을 검사할 수 없다면 -1을 출력한다.
제한
- 기계의 수 0 < T ≤ 10
- 검사해야 할 기능의 수 0 < n ≤ 500
- 테스트 데이터의 수 0 < m ≤ 15