1367: 你好,世界

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:7 Solved:1

Description

在软件测试流程中,每个测试用例都可能覆盖部分代码模块。我们用一个二维数组 cases 来描述测试用例的模块覆盖情况:

  • cases 的长度为测试用例的总数,每个元素代表一个独立的测试用例;
  • 对于 cases[i][j],其值为 1 表示第 i 个测试用例覆盖了第 j 个代码模块,值为 0 表示未覆盖。

请你找出一个最小规模的测试用例集合,使得该集合中的测试用例能够覆盖所有的代码模块。若不存在这样的集合(即存在无法被任何测试用例覆盖的代码模块),请返回 -1。

Input

输入首先为n m代表行数和列数。

然后输入一个二维整数数组 cases满足:

  1. cases 的行数 n(测试用例数)满足 1 ≤ n ≤ 10
  2. cases 的列数 m(代码模块数)满足 1 ≤ m ≤ 10
  3. 数组中每个元素仅为 0 或 1。

Output

输出一个整数:

  • 若存在满足条件的最小测试用例集合,返回该集合的大小;
  • 若不存在,返回 -1。

Sample Input Copy

4 3
1 0 0
0 1 0
0 0 1
1 1 0

Sample Output Copy

2