题目描述

小兔需要完成 $n$ 门课程，编号为 $1$ 到 $n$。课程涉及 $k$ 个知识点，编号为 $1$ 到 $k$。最初，小兔对每个知识点的掌握程度均为 $0$。

每门课程都有学习要求。对于第 $i$ 门课程，小兔对第 $j$ 个知识点的掌握程度必须不小于 $r_{i,j}$，才能完成这门课程。完成第 $i$ 门课程后，他对第 $j$ 个知识点的掌握程度会增加 $u_{i,j}$。

小兔可以任意选择完成课程的顺序，但每门课程至多完成一次。你需要帮助小兔求出，他最多可以完成多少门课程。

输入格式

输入的第一行包含两个正整数 $n,k$，分别表示课程数和知识点数。

接下来 $n$ 行，其中第 $i$ 行包含 $k$ 个非负整数 $r_{i,1},r_{i,2},\ldots,r_{i,k}$，依次表示完成第 $i$ 门课程对各知识点的掌握程度要求。

接下来 $n$ 行，其中第 $i$ 行包含 $k$ 个非负整数 $u_{i,1},u_{i,2},\ldots,u_{i,k}$，依次表示完成第 $i$ 门课程后对各知识点的掌握程度增加量。

输出格式

输出一行一个非负整数，表示小兔最多可以完成的课程数。

输入输出样例

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

说明/提示

样例 1 解释

小兔最初只能完成第 $1$ 门课程，完成后对三个知识点的掌握程度依次为 $7,8,2$。此时无法完成其余课程，所以答案为 $1$。

该样例满足测试点 $4\sim10$ 的约束条件。

样例 2 解释

小兔可以按照 $3,1,2,4$ 的顺序完成所有课程，所以答案为 $4$。

该样例满足测试点 $4\sim10$ 的约束条件。

样例 3

见附件中的 topical/topical3.in 与 topical/topical3.ans。

该样例满足测试点 $4\sim10$ 的约束条件。

数据范围

对于所有测试数据，均有：

• $1\le n,k\le10^6$，$n\times k\le10^6$；
• 对于所有 $i,j$（$1\le i\le n$，$1\le j\le k$），均有 $0\le r_{i,j},u_{i,j}\le10^9$。

附件

下载附加样例（topical.zip）