Description

There are $N$ school idol groups, possibly from schools numbered $1$ to $N$. Each school may have multiple groups participating, or none. After all groups finish performing, a popularity vote is held.

We have two popularity rankings: one at halftime and one at the end. Each ranking is sorted from higher to lower popularity, and shows each group's school ID (but you do not know which specific group).

However, the final ranking is not quite correct. Based on the facts that a group's final popularity is not lower than its halftime popularity, and a group's school does not change, the final ranking produces contradictions.

The statistician, trying to avoid blame, wants to modify as few school IDs in the final ranking as possible (popularity values cannot be changed) to eliminate contradictions. What is the minimum number of modifications?

Input Format

• The first line contains an integer $N$, the number of groups.
• The next $N$ lines each contain two integers, $Ta_i, Pa_i$, representing the halftime popularity ranking. $Ta_i$ is the school ID, and $Pa_i$ is the popularity value. These lines are sorted in descending order by popularity.
• The next $N$ lines each contain two integers, $Tb_i, Pb_i$, representing the final popularity ranking. These lines are also sorted in descending order by popularity.

Output Format

Output a single integer: the answer.

3
3 500
2 200
1 100
1 1000
3 700
3 400

1

Hint

Constraints

• For 20% of the testdata, $N \le 16$, time limit 0.5 s.
• For 40% of the testdata, $N \le 50$, time limit 1 s.
• For 70% of the testdata, $N \le 5000$, time limit 1 s.
• For all testdata, $N \le 200000$, and all popularity values are $\le 10^9$. The last 3 test points have a 3 s time limit.

Translated by ChatGPT 5