← 返回题目列表

AtCoder · tessoku_book_w

A23. 全部免费

中文机器翻译题面 查看原题

配点: 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

即使使用了所有优惠券,也无法免费购买所有商品。 有