题目描述

译自 NOISG 2023 Final T1. Topical

兔子本森正在飞行学校学习！

他需要完成 $n$ 个模块，编号从 $1$ 到 $n$。飞行课程包含 $k$ 个主题，编号从 $1$ 到 $k$。由于本森是飞行新手，他对每个主题的初始知识量为零。

这 $n$ 个模块每个都有完成所需的知识要求。具体来说，要完成模块 $i$，本森需要对所有主题 $j$ 至少具备 $r[i][j]$ 的知识量。

完成一个模块还能让本森在某些主题上获得知识。完成模块 $i$ 后，他将在主题 $j$ 上获得 $u[i][j]$ 的知识量。

形式上，设本森在主题 $j$ 的知识量为 $p[j]$。初始时，所有 $j$ 的 $p[j]=0$。只有当每个主题 $j$ 满足 $p[j] \geq r[i][j]$ 时，他才能完成模块 $i$。完成模块 $i$ 后，每个主题 $j$ 的 $p[j]$ 将增加 $u[i][j]$。

本森可以按任意顺序完成模块，但每个模块最多只能完成一次。帮助本森确定他最多能完成的模块数量。

输入格式

程序需从标准输入读取数据。

输入的第一行包含两个空格分隔的整数 $n$ 和 $k$。

接下来的 $n$ 行，第 $i$ $(1 \leq i \leq n)$ 行包含 $k$ 个空格分隔的整数 $r[i][1], r[i][2], \ldots, r[i][k]$，表示完成模块 $i$ 所需的知识要求。

接下来的 $n$ 行，第 $i$ $(1 \leq i \leq n)$ 行包含 $k$ 个空格分隔的整数 $u[i][1], u[i][2], \ldots, u[i][k]$，表示完成模块 $i$ 后获得的知识量。

输出格式

程序需向标准输出输出结果。

输出一个整数，表示本森最多能完成的模块数量。

输出仅包含一个整数，不应包含任何额外文本，如 Enter a number 或 The answer is。

3 3
0 0 0
7 9 2
7 8 9
7 8 2
7 7 7
8 10 9

1

本森只能完成模块 $1$，其知识要求为 $[0,0,0]$。完成后，他在三个主题上分别获得 $7, 8, 2$ 的知识量，但 $p=[7,8,2]$ 不足以完成其他模块。由于没有其他顺序能让本森完成超过 $1$ 个模块，最终答案为 $1$。

这个样例满足子任务 $2,4$ 的限制。

4 3
5 1 0
0 1 5
0 0 0
7 7 7
0 5 6
1 1 1
8 2 0
8 1 4

4

本森可以按照顺序 $3, 1, 2, 4$ 完成所有 4 个模块：

• 初始知识 $p=[0,0,0]$，可完成模块 $3$，知识增加 $u[3]=[8,2,0]$。
• 知识 $p=[8,2,0]$，可完成模块 $1$，知识增加 $u[1]=[0,5,6]$。
• 知识 $p=[8,7,6]$，可完成模块 $2$，知识增加 $u[2]=[1,1,1]$。
• 知识 $p=[9,8,7]$，可完成模块 $4$，知识增加 $u[4]=[8,1,4]$。

由于本森能完成所有 $4$ 个模块，答案为 $4$。

这个样例满足子任务 $2,4$ 的限制。

5 5
14 11 15 7 15
0 0 0 0 0
9 9 14 2 13
4 3 6 1 0
2 4 7 0 0
5 5 0 0 13
4 4 7 1 0
4 1 0 2 1
2 5 0 2 1
4 0 7 2 12

4

本森可以按照顺序 $2, 4, 5, 3$ 完成 $4$ 个模块：

• 初始知识 $p=[0,0,0,0,0]$，可完成模块 $2$，知识增加 $u[2]=[4,4,7,1,0]$。
• 知识 $p=[4,4,7,1,0]$，可完成模块 $4$，知识增加 $u[4]=[2,5,0,2,1]$。
• 知识 $p=[6,9,7,3,1]$，可完成模块 $5$，知识增加 $u[5]=[4,0,7,2,12]$。
• 知识 $p=[10,9,14,5,13]$，可完成模块 $3$，知识增加 $u[3]=[4,1,0,2,1]$。

完成后，知识为 $p=[14,10,14,7,14]$，不足以完成其他模块。由于没有其他顺序能让本森完成超过 $4$ 个模块，最终答案为 $4$。

这个样例满足子任务 $2,4$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq n, k \leq 10^{6}$
• $n \cdot k \leq 10^{6}$
• $0 \leq u[i][j], r[i][j] \leq 10^{9}$（对于所有 $1 \leq i \leq n$ 和 $1 \leq j \leq k$）。

详细子任务附加限制及分值如下表所示：