Description

Koishi likes segments.

Each of her $n$ segments can be represented as a closed interval $[l, r]$ on the number line. Koishi likes to put all the segments on the number line and then count how many segments cover certain points.

Seeing how happily she plays with segments, Flandre throws her a problem:

There are $m$ points on the number line that suddenly get excited. If a point is covered by more than $x$ segments, it will feel terrible and criticize Koishi.

Koishi is very kind. To avoid making the points feel bad and to make herself happy, she wants to place as many segments on the number line as possible.

As usual, Koishi pretends she cannot solve this problem, so she asks you for help, and promises to give you a phone call if you solve it.

Input Format

The first line contains two integers $n, m$, denoting the number of segments to insert and the number of excited points.

Each of the next $n$ lines contains two integers $l, r$ ($l \le r$), denoting the endpoints of a segment $[l, r]$.

Each of the next $m$ lines contains two integers $p, x$, meaning that the point at position $p$ gets excited and requires that it should not be covered by more than $x$ segments.

Output Format

Output a single integer, denoting the maximum number of segments that can be placed.

4 3
1 3
2 4
5 7
6 8
2 5
3 1
6 2

3

Hint

• For 20% of the testdata, $1 \le n, m \le 20$.
• For 60% of the testdata, $1 \le n, m \le 100$.
• For 80% of the testdata, $1 \le n, m \le 5000$.
• Constraints: $1 \le x \le n \le 2\times 10^5$, $1 \le m \le 4\times 10^5$, $|l|, |r|, |p| \le 10^7$.
• If a point gets excited multiple times, Koishi should satisfy its stricter requirement (i.e., when $p$ is the same, take the minimum $x$).
• Please use fast I/O appropriately.

Translated by ChatGPT 5