星际探险

题目描述

星际探险队计划从 n 名候选者中挑选队员组成小队，每名候选者只能入选一次。

飞船上有 m 个关键系统，第 i 名候选者的加入会对第 j 个系统的状态值产生 (ai, j) 的影响，影响可正可负。

探险安全条例要求，最终小队组成后，每个系统的状态值总和都必须不低于 0，否则飞船无法维持安全航行。

在满足该要求的前提下，希望小队的人数尽可能多，请输出这个最大人数。若不存在任何满足条件的选人方案，输出0。

输入格式

第一行：两个整数表示 n 与 m；

第二行到第 n+1 行：第 i+1 行有 m 个整数，表示 (ai,1)、(ai,2)、……、(ai,m)。

输出格式

单个整数：表示答案。

输入样例

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

输出样例

4

说明提示：

1≤n、m≤16，1,000,000≤ (ai, j) ≤1,000,000。

限制：

时间限制：1000ms，内存限制：256MiB