Dimensional Debugging

Interview

Time limit2sMemory limit2048 MB

Summary

Count algorithms verifiable by BFS from those with all L_i equal to 0, where algorithm A verifies B when L_B is at most H_A in every parameter.

Level: Medium4 of 10
Topics: Graph, BFS
Solved: No attempts yet

Problem

After struggling with this one problem for days, you have had enough! You are determined to find the bug in your algorithm once and for all! To do so, you will start all over. From scratch. At least you are sure you know the correct answer in the most trivial case: the answer in $(0,0,\dots,0)$ is $0$ .

You will re-solve the problem, which takes $k$ parameters, using $n$ simpler but slower algorithms. Each algorithm has two bounds for every parameter $i$ ( $L_i$ and $H_i$ ). An algorithm is only fast enough to run on inputs $(x_1,\dots,x_k)$ where $x_i \leq H_i$ for all parameters $i$ . You are confident the implementation of an algorithm is correct if you can verify its correctness at least once on an input $(x_1,\dots,x_k)$ where $x_i \geq L_i$ for all parameters $i$ . To do so, you will need another algorithm that you already proved to be correct and can handle such large inputs, or your knowledge of the answer for $(0,0,\dots,0)$ .

Given a list of algorithms and their bounds, find the number of algorithms you are sure are correctly implemented.

As an example, consider the first sample case shown in Figure D.1 on the left. The first algorithm (red, bottom left) can be used to verify the correctness of the second (yellow, top left) and third (blue, bottom right) algorithms. No algorithm can be used to verify the correctness of the fourth algorithm (grey, top right).

Figure D.1: The algorithms to be tested in samples 1 and 2, respectively. The boxes indicate the parameters where an algorithm must be tested, while the lighter background indicates the region where an algorithm can be used to verify other algorithms.

Input

The input consists of:

One line with two integers $n$ and $k$ ( $1\leq n\leq 1000$ , $1\leq k\leq 10$ ), the number of algorithms to test and the number of parameters.
Then follow $n$ pairs of lines:
- One line with $k$ integers $L_1, \dots, L_k$ ( $0\leq L_i \leq 10^9$ for all $i$ ).
- One line with $k$ integers $H_1, \dots, H_k$ ( $0\leq H_i \leq 10^9$ for all $i$ ).
It is guaranteed that $L_i \leq H_i$ for all $1 \leq i\leq k$ .

Output

Output the number of algorithms of which you can verify the correctness.

Examples4

Example 1
Input
```
4 2
0 0
4 3
1 2
4 6
3 1
7 2
6 4
8 5
```
Expected output
```
3
```
Example 2
Input
```
4 2
0 0
4 3
0 2
5 5
7 1
8 2
5 5
8 6
```
Expected output
```
4
```
Example 3
Input
```
3 1
1
10
10
100
0
1
```
Expected output
```
3
```

Example 4

Input

Expected output