Benson's Pilot School Tests

Rabbit Benson is attending pilot school! He must complete \(n\) tests, numbered from \(1\) to \(n\). Each test assesses his performance in \(k\) subjects. Initially, for all subjects \(j\), his ability \(p_j = 0\).

For the \(i\)-th test and the \(j\)-th subject, there is a minimum required ability \(r_{i,j}\). Benson can only take a test if his current ability in every subject satisfies \(p_j \ge r_{i,j}\) for all \(1 \le j \le k\). When he successfully completes a test, his ability in the \(j\)-th subject increases by \(u_{i,j}\); that is, his ability is updated as \(p_j \leftarrow p_j + u_{i,j}\) for every \(j\).

He may attempt the tests in any order, but each test can only be completed once. Your task is to determine the maximum number of tests Benson can complete.

inputFormat

The first line contains two integers \(n\) and \(k\), representing the number of tests and the number of subjects respectively.

This is followed by \(2n\) lines detailing each test:

• The next \(n\) lines each contain \(k\) integers: \(r_{i,1}, r_{i,2}, \dots, r_{i,k}\) for \(i = 1 \dots n\).
• The following \(n\) lines each contain \(k\) integers: \(u_{i,1}, u_{i,2}, \dots, u_{i,k}\) for \(i = 1 \dots n\).

outputFormat

Output a single integer, the maximum number of tests that Benson can complete.

sample

3 2
0 0
1 1
2 3
1 1
1 2
1 1

3