A23 - All Free Editorial /

Time Limit: 1 sec / Memory Limit: 1024 MB

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

すべてのクーポン券を使っても、全品物を無料で買うことはできません。