5222 : A23 - 올 프리 (All Free)
•시간제한: 3.000 S
•메모리제한: 1024 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
정보 상점에서는 $N$ 종류의 상품을 취급하고 있습니다. 각 상품은 1부터 $N$ 까지 번호가 매겨져 있습니다.
이 상점에서는 지정된 몇 개의 상품을 무료로 살 수 있는 쿠폰을 배부하고 있습니다.
타로는 $M$ 장의 쿠폰을 가지고 있습니다. 쿠폰 $i$ ($i = 1, 2, \dots, M$)의 정보는 다음과 같습니다.
최소 몇 장의 쿠폰을 사용하여 $N$ 종류의 모든 상품을 살 수 있는지 구하십시오.
[제약 조건]
• $1 \le N \le 10$
• $1 \le M \le 100$
• $0 \le A_{i, j} \le 1$
• 입력되는 모든 값은 정수입니다.
이 상점에서는 지정된 몇 개의 상품을 무료로 살 수 있는 쿠폰을 배부하고 있습니다.
타로는 $M$ 장의 쿠폰을 가지고 있습니다. 쿠폰 $i$ ($i = 1, 2, \dots, M$)의 정보는 다음과 같습니다.
- $A_{i, j} = 1$ 일 때: 상품 $j$ 는 무료 구매 대상에 포함됨.
- $A_{i, j} = 0$ 일 때: 상품 $j$ 는 무료 구매 대상에 포함되지 않음.
최소 몇 장의 쿠폰을 사용하여 $N$ 종류의 모든 상품을 살 수 있는지 구하십시오.
[제약 조건]
• $1 \le N \le 10$
• $1 \le M \le 100$
• $0 \le A_{i, j} \le 1$
• 입력되는 모든 값은 정수입니다.
입력 설명
첫째 줄에 $N$ 과 $M$ 이 주어집니다.
다음 $M$ 개 줄에 각 쿠폰의 정보 $A_{i, 1}, A_{i, 2}, \dots, A_{i, N}$ 이 공백으로 구분되어 주어집니다.
다음 $M$ 개 줄에 각 쿠폰의 정보 $A_{i, 1}, A_{i, 2}, \dots, A_{i, N}$ 이 공백으로 구분되어 주어집니다.
출력 설명
모든 상품을 사기 위해 필요한 최소 쿠폰 개수를 출력하십시오. 모든 쿠폰을 사용해도 불가능한 경우 `-1`을 출력하십시오.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 4
0 0 1
0 1 0
1 0 0
1 1 0
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2