Sunscreen

Interview

Time limit1sMemory limit128 MB

Summary

Each cow accepts an SPF interval, each bottle has an SPF value and capacity; assign bottles to maximize the number of cows covered.

Level: Medium5 of 10
Topics: Greedy, Sorting, Intervals, Two pointers
Solved: No attempts yet

Problem

To avoid an unsightly burn while tanning at the beach, each of the $C$ cows ( $1 \le C \le 2500$ ) must cover her hide with sunscreen. Cow $i$ works only with a range of SPF ratings, given by a minimum $\text{minSPF}_i$ and a maximum $\text{maxSPF}_i$ ( $1 \le \text{minSPF}_i \le 1000$ , $\text{minSPF}_i \le \text{maxSPF}_i \le 1000$ ). If the SPF rating is too low the cow gets sunburned; if it is too high the cow does not tan at all.

The cows share a picnic basket holding $L$ bottles of sunscreen lotion ( $1 \le L \le 2500$ ). Bottle $i$ has an SPF rating $\text{SPF}_i$ ( $1 \le \text{SPF}_i \le 1000$ ) and can be applied to at most $\text{cover}_i$ cows. Each cow may use lotion from only one bottle.

Cow $i$ is protected by bottle $j$ if and only if $\text{minSPF}_i \le \text{SPF}_j \le \text{maxSPF}_i$ . What is the maximum number of cows that can protect themselves while tanning with the available lotion?

Input

Line 1: Two space-separated integers, $C$ and $L$ .
Lines 2 to $C+1$ : Line $i+1$ describes cow $i$ with two integers, $\text{minSPF}_i$ and $\text{maxSPF}_i$ .
Lines $C+2$ to $C+L+1$ : Each line describes one lotion bottle with two space-separated integers, $\text{SPF}_i$ and $\text{cover}_i$ .

Output

Print a single integer: the maximum number of cows that can be protected while tanning.

Examples4

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