题目描述

有 $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​},…,a_{i,m​}$

输出格式

单个整数：表示答案。

样例 #1

样例输入 #1

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

样例输出 #1

4

提示

$1≤n,m≤16$

$−1,000,000≤a_{i,j​}≤1,000,000$