Nous sommes en 21XX. La programmation compétitive est largement reconnue comme un sport de l'esprit et fait souvent l'objet de reportages dans les médias, notamment à la télévision et dans les journaux.

Vous êtes journaliste au journal JOI et vous êtes chargé des articles sur la programmation compétitive.

Hier, un concours international de programmation compétitive réunissant $N$ participants a eu lieu. Pour rédiger un article sur ce concours, vous avez reçu les informations suivantes.

• Comme aux Olympiades internationales d'informatique, les participants à ce concours venaient de plusieurs pays. Chaque pays porte un numéro compris entre $1$ et $N$. Plusieurs participants peuvent venir du même pays. Certains pays peuvent aussi n'avoir aucun participant.
• Le concours dure 5 heures.
• Le score obtenu par un participant pendant le concours ne diminue jamais par la suite.
• Deux heures après le début du concours, aucun participant n'avait le même score qu'un autre. Dans le classement à cet instant, le participant à la $i$-ème place ($1 \le i \le N$) venait du pays $A_i$ et avait un score de $B_i$ points.
• À la fin du concours, aucun participant n'avait le même score qu'un autre. Dans le classement final, le participant à la $i$-ème place ($1 \le i \le N$) venait du pays $C_i$ et avait un score de $D_i$ points.

Cependant, au moment de rédiger l'article, vous découvrez un problème dans l'affichage des pays d'origine du classement. Les pays d'origine des participants ont peut-être été affichés incorrectement. On sait que les scores affichés étaient corrects.

Vous décidez donc de déduire des classements cohérents en apportant le moins de corrections possible aux informations reçues : le pays d'origine d'un même participant ne doit pas changer pendant le concours, et son score ne doit pas diminuer. Autrement dit, vous voulez modifier le moins possible des $2N$ valeurs $A_1,\ldots,A_N,C_1,\ldots,C_N$ pour satisfaire la condition suivante :

• Il existe une permutation $x_1,x_2,\ldots,x_N$ de $1,2,\ldots,N$ telle que, pour tout $i=1,2,\ldots,N$, on ait $A_i=C_{x_i}$ et $B_i \le D_{x_i}$.

Quel est le nombre minimal de corrections que vous devez apporter aux informations reçues ?

Tâche

Étant donnés le nombre de participants au concours et les classements deux heures après le début du concours et à la fin du concours, écrivez un programme qui calcule le nombre minimal d'informations de pays d'origine à modifier pour rendre les classements cohérents.

Entrée

Lisez les données suivantes sur l'entrée standard.

• La première ligne contient un entier $N$, indiquant que $N$ participants ont pris part au concours.
• La $i$-ème ligne ($1 \le i \le N$) des $N$ lignes suivantes contient deux entiers $A_i,B_i$ séparés par un espace. Cela signifie que, dans le classement deux heures après le début du concours, le participant à la $i$-ème place était affiché comme venant du pays $A_i$ et avait obtenu $B_i$ points.
• La $i$-ème ligne ($1 \le i \le N$) des $N$ lignes suivantes contient deux entiers $C_i,D_i$ séparés par un espace. Cela signifie que, dans le classement final, le participant à la $i$-ème place était affiché comme venant du pays $C_i$ et avait obtenu $D_i$ points.

Sortie

Écrivez sur une ligne de la sortie standard le nombre minimal d'informations de pays d'origine à modifier pour rendre les classements cohérents.

Contraintes

Toutes les données d'entrée satisfont les conditions suivantes.

• $2 \le N \le 200\,000$.
• $1 \le A_i \le N$ ($1 \le i \le N$).
• $0 \le B_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $B_i>B_{i+1}$ ($1 \le i \le N-1$).
• $1 \le C_i \le N$ ($1 \le i \le N$).
• $0 \le D_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $D_i>D_{i+1}$ ($1 \le i \le N-1$).
• Il est possible de rendre les classements cohérents en modifiant certaines des valeurs $A_1,\ldots,A_N,C_1,\ldots,C_N$.

Sous-tâches

Sous-tâche 1 [15 points]

• $N \le 16$.

Sous-tâche 2 [15 points]

• $N \le 50$.

Sous-tâche 3 [30 points]

• $N \le 5000$.

Sous-tâche 4 [40 points]

Il n'y a aucune contrainte supplémentaire.

Exemples

Entrée 1

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

Sortie 1

1

Remarque

En remplaçant la valeur de $C_3$ par $2$, on obtient les classements cohérents suivants :

• Le participant du pays $3$, qui était premier avec $500$ points deux heures après le début du concours, termine deuxième avec $700$ points.
• Le participant du pays $2$, qui était deuxième avec $200$ points deux heures après le début du concours, termine troisième avec $400$ points.
• Le participant du pays $1$, qui était troisième avec $100$ points deux heures après le début du concours, termine premier avec $1000$ points.

Si l'on remplaçait plutôt la valeur de $C_2$ par $2$, les classements seraient incohérents : le participant du pays $3$, qui avait obtenu $500$ points deux heures après le début du concours, n'aurait plus que $400$ points à la fin du concours.

Il est impossible d'obtenir des classements cohérents avec moins d'une correction ; on affiche donc $1$.

Entrée 2

3
3 3
3 2
1 1
3 4
3 2
1 1

Sortie 2

0

Remarque

Dans ce cas, les classements sont déjà cohérents sans modifier les pays d'origine. Remarquez que certains participants peuvent ne pas avoir augmenté leur score depuis l'instant situé deux heures après le début du concours. Remarquez aussi que plusieurs participants du classement peuvent avoir le même pays d'origine.

Entrée 3

6
1 70
4 50
1 30
2 20
1 10
3 0
6 100
2 90
1 80
2 60
4 40
1 10

Sortie 3

3

Remarque

Dans cet exemple, en remplaçant $A_1$ par $2$, $A_6$ par $4$ et $C_1$ par $4$, on obtient des classements cohérents.