Topical

벤슨 토끼는 조종사 학교에 다니고 있다.

벤슨이 이수해야 할 모듈은 $n$개이며, 1번부터 $n$번까지 번호가 붙어 있다. 비행에는 $k$개의 주제가 있으며, 1번부터 $k$번까지 번호가 붙어 있다. 벤슨은 비행이 처음이라서 모든 주제의 지식이 0인 상태에서 시작한다.

각 모듈에는 요구 지식 기준이 있다. 모듈 $i$를 이수하려면 모든 주제 $j$에서 최소 $r[i][j]$만큼의 지식이 있어야 한다. 모듈 $i$를 이수하면 모든 주제 $j$의 지식이 $u[i][j]$만큼 늘어난다.

형식으로 나타내면, 주제 $j$에서 벤슨의 지식을 $p[j]$라고 하자. 처음에는 모든 $j$에 대해 $p[j] = 0$이다. 모든 주제 $j$에 대해 $p[j] \ge r[i][j]$일 때만 모듈 $i$를 이수할 수 있다. 모듈 $i$를 이수하면 각 주제 $j$에서 $p[j]$가 $u[i][j]$만큼 증가한다.

벤슨은 모듈을 어떤 순서로든 이수할 수 있지만, 각 모듈은 최대 한 번만 이수할 수 있다. 벤슨이 이수할 수 있는 모듈의 최대 개수를 구하라.

첫째 줄에 공백으로 구분된 두 정수 $n$과 $k$가 주어진다.

이어서 $n$개의 줄이 주어진다. 그중 $i$번째 줄에는 공백으로 구분된 $k$개의 정수 $r[i][1], r[i][2], \dots, r[i][k]$가 들어 있다.

그다음 $n$개의 줄이 주어진다. 그중 $i$번째 줄에는 공백으로 구분된 $k$개의 정수 $u[i][1], u[i][2], \dots, u[i][k]$가 들어 있다.

벤슨이 이수할 수 있는 모듈의 최대 개수를 정수 하나로 출력한다.

$1 \le n, k \le 10^6$

$n \cdot k \le 10^6$

모든 $1 \le i \le n$과 $1 \le j \le k$에 대해 $0 \le u[i][j], r[i][j] \le 10^9$이다.