题目描述

兔子 Benson 正在上飞行员学校！

他需要完成 $n$ 场测试，由 $1\sim n$ 编号。对于每场测试，有 $k$ 个科目。对于每个科目，Benson 有一个能力值 $p_j$。由于 Benson 还是一名新手，他对于每个科目的初始能力值均为 $0$。

对于每场测试的每个科目，均有一个能力值下限 $r_{i, j}$。而为了完成第 $i$ 场测试，需要满足他每个科目的能力值都不低于这个下限。

若成功完成第 $i$ 场测试，他的能力值将获得提升，且第 $j$ 个科目的能力值将提升 $u_{i, j}$。

形式化地：初始，对于所有 $j$，有 $p_j=0$。Benson 能完成一场测试，当且仅当对于所有 $j$，都有 $r_{i, j}\leq p_j$；完成该场测试后，对于所有 $j$，$p_j$ 的值将增加 $u_{i, j}$。

他可以任意选择完成测试的顺序，但每场测试只能完成一次。请帮助他计算他最多能完成多少场测试。

输入格式

第一行两个正整数 $n, k$，用空格隔开。

接下来 $n$ 行，第 $i$ 行包含 $k$ 个整数 $r_{i, 1}, r_{i, 2}, \cdots, r_{i, k}$，表示完成第 $i$ 场测试的能力值下限。

接下来 $n$ 行，第 $i$ 行包含 $k$ 个整数 $u_{i, 1}, u_{i, 2}, \cdots, u_{i, k}$，表示完成第 $i$ 场测试后能力值的增加量。

输出格式

输出一行一个整数，表示 Benson 最多能完成的测试数量。

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

1

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

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

提示

样例 #1 解释

Benson 只能完成第一场测试，其要求为 $[0, 0, 0]$。完成后，他的能力值将变为 $[7, 8, 2]$。此时他不能完成任何一场其余的测试，故答案为 $1$。

数据范围

对于 $100\%$ 的数据：

• $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$。

注：由于洛谷限制，数据不完全按照原题分配子任务。