题目描述

有 $n$ 种材料，我们需要挑选其中的一些材料组成合金，每种材料只能使用一次。

合金具有 $m$ 种性质，每种性质可以用一个整数衡量。每种材料都会影响所有的属性。如果使用了第 $i$ 种材料，会使第 $j$ 种性质增加 $a_{i,j}$，注意 $a_{i,j}$ 可正可负。

若需要所有属性的最后数值都不低于 $0$，则最多可以使用多少种材料？若没有办法用任何材料的组合，输出 $0$。

输入格式

• 第一行：两个整数表示 $n$ 与 $m$
• 第二行到第 $n+1$ 行：第 $i+1$ 行有 $m$ 个整数，表示 $a_{i,1}, a_{i,2}, \dots, a_{i,m}$

输出格式

• 单个整数：表示答案。

4 3
1 1 -2
1 -2 1
-2 1 1
2 2 2

4

数据范围

• $1\leq n,m\leq 16$
• $-1,000,000\leq a_{i,j} \leq 1,000,000$