配点: 1000 点
注意
根据书籍的版本,书中的代码可能不正确。请参阅勘误表。
問題文
在信息商店
我们处理 N 类型的物品。每个
它们的编号最大为 1 减去 N 。
本店赠送优惠券,可让您免费购买某些指定商品。
太郎君是 M 优惠券。
优惠券 i (i = 1, 2, \cdots, M) 的信息如下。
- A_{i, j} = 1 :货物 j 包含在可免费购买的物品中。
- A_{i, j} = 0 :货物 j 不包含在可免费购买的物品中。
通过使用最低数量的优惠券,N 我可以购买所有种类的物品吗?
制約
- 1 \leq N \leq 10
- 1 \leq M \leq 100
- 0 \leq A_{i, j} \leq 1
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N M
A_{1,1} A_{1,2} \cdots A_{1,N}
A_{2,1} A_{2,2} \cdots A_{2,N}
:
A_{M,1} A_{M,2} \cdots A_{M,N}
出力
请输出所需的最少优惠券数量。
但是,
运算前设定中包含的N 如果没有办法免费购买各类物品,改为
最好使用 -1 请输出。
入力例 1
3 4 0 0 1 0 1 0 1 0 0 1 1 0
出力例 1
2
优惠券 1, 4 。
入力例 2
10 2 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0
出力例 2
-1
即使使用了所有优惠券,也无法免费购买所有商品。 有