Topical

문제

Benson the Rabbit is attending pilot school!

He has $nn$ modules to complete, numbered from $11$ to $nn$. There are $kk$ topics in flying numbered from $11$ to $kk$. As Benson is new to flying, he starts with zero knowledge in each topic.

Each of these $nn$ modules have a knowledge requirement to complete them. In particular, to complete module $ii$, Benson requires at least $r[i][j]r[i][j]$ knowledge of topic $jj$ for all topics $jj$.

Completing a module also allows Benson to gain knowledge in some topics. After completing module $ii$, he will gain $u[i][j]u[i][j]$ knowledge in topic $jj$.

Formally, let Benson’s knowledge in topic $jj$ be $p[j]p[j]$. Initially, $p[j]=0p[j]\; =\; 0$ for all $jj$. He can only complete a module $ii$ if p[j] ≥ r[i][j] for every topic $jj$. After completing module $ii$, the value of $p[j]p[j]$ increases by $u[i][j]u[i][j]$ for each topic $jj$.

Benson may complete the modules in any order, but each module may only be completed at most once. Help Benson determine the maximum number of modules he can complete.

입력

The first line of input contains $22$ space-separated integers, $nn$ and $kk$.

Then, $nn$ lines will follow. The $ii$-th (1 ≤ i ≤ n) of these lines contains $kk$ spaced integers $r[i][1],r[i][2],\dots ,r[i][k]r[i][1],\; r[i][2],\; \backslash dots\; ,\; r[i][k]$, denoting the knowledge requirements to complete module $ii$.

Another $nn$ lines follow. The $ii$-th (1 ≤ i ≤ n) of these lines contains $kk$ spaced integers $u[i][1],u[i][2],\dots ,u[i][k]u[i][1],\; u[i][2],\; \backslash dots\; ,\; u[i][k]$, denoting the knowledge gained after completing module $ii$.

출력

The output should contain one integer, the maximum number of modules Benson can complete.

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