Wir schreiben das Jahr 21XX. Wettbewerbsprogrammierung ist allgemein als Denksport anerkannt und wird häufig in Medien wie Fernsehen und Zeitungen behandelt.

Du bist Reporter der Zeitung JOI und für Artikel über Wettbewerbsprogrammierung zuständig.

Gestern fand ein internationaler Programmierwettbewerb mit $N$ Teilnehmern statt. Für deinen Artikel darüber hast du folgende Informationen erhalten:

• Wie bei der Internationalen Informatikolympiade nahmen Teilnehmer aus mehreren Ländern teil. Die Länder tragen Nummern von $1$ bis $N$. Aus einem Land können mehrere Teilnehmer stammen. Manche Länder haben möglicherweise keine Teilnehmer.
• Die Wettbewerbsdauer betrug 5 Stunden.
• Einmal während des Wettbewerbs erreichte Punktzahlen wurden später nicht verringert.
• Zwei Stunden nach Wettbewerbsbeginn hatten keine zwei Teilnehmer dieselbe Punktzahl. In der damaligen Rangliste stammte der Teilnehmer auf Platz $i$ ($1 \le i \le N$) aus Land $A_i$ und hatte $B_i$ Punkte.
• Am Wettbewerbsende hatten keine zwei Teilnehmer dieselbe Punktzahl. In der endgültigen Rangliste stammte der Teilnehmer auf Platz $i$ ($1 \le i \le N$) aus Land $C_i$ und hatte $D_i$ Punkte.

Als du den Artikel schreiben wolltest, stellte sich jedoch heraus, dass die Anzeige der Herkunftsländer in der Rangliste fehlerhaft war. Die Herkunftsländer könnten falsch angezeigt worden sein. Es ist bekannt, dass die angezeigten Punktzahlen korrekt waren.

Daher möchtest du die erhaltenen Informationen mit möglichst wenigen Änderungen zu widerspruchsfreien Ranglisten ergänzen: Das Herkunftsland eines Teilnehmers darf sich während des Wettbewerbs nicht ändern, und seine Punktzahl darf nicht sinken. Du möchtest also möglichst wenige der $2N$ Werte $A_1,\ldots,A_N,C_1,\ldots,C_N$ ändern, sodass die folgende Bedingung gilt:

• Es gibt eine Permutation $x_1,x_2,\ldots,x_N$ der Zahlen $1,2,\ldots,N$, für die bei jedem $i=1,2,\ldots,N$ sowohl $A_i=C_{x_i}$ als auch $B_i \le D_{x_i}$ gilt.

Wie viele Einträge der erhaltenen Informationen musst du mindestens ändern?

Aufgabe

Gegeben sind die Teilnehmerzahl und Informationen über die Ranglisten zwei Stunden nach Wettbewerbsbeginn sowie am Wettbewerbsende. Schreibe ein Programm, das die minimale Anzahl von Änderungen an den Herkunftsländern berechnet, die erforderlich ist, um widerspruchsfreie Ranglisten zu erhalten.

Eingabe

Lies die folgenden Daten von der Standardeingabe.

• Die erste Zeile enthält eine ganze Zahl $N$. Sie gibt an, dass $N$ Teilnehmer am Wettbewerb teilgenommen haben.
• Die $i$-te Zeile ($1 \le i \le N$) der folgenden $N$ Zeilen enthält zwei durch Leerzeichen getrennte ganze Zahlen $A_i,B_i$. In der Rangliste zwei Stunden nach Wettbewerbsbeginn wurde für den Teilnehmer auf Platz $i$ das Herkunftsland $A_i$ angezeigt; er hatte $B_i$ Punkte.
• Die $i$-te Zeile ($1 \le i \le N$) der folgenden $N$ Zeilen enthält zwei durch Leerzeichen getrennte ganze Zahlen $C_i,D_i$. In der Rangliste am Wettbewerbsende wurde für den Teilnehmer auf Platz $i$ das Herkunftsland $C_i$ angezeigt; er hatte $D_i$ Punkte.

Ausgabe

Gib in einer Zeile der Standardausgabe die minimale Anzahl erforderlicher Änderungen an den Herkunftsländern aus, durch die die Ranglisten widerspruchsfrei werden.

Beschränkungen

Alle Eingabedaten erfüllen die folgenden Bedingungen.

• $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$).
• Durch Änderungen an einigen der Werte $A_1,\ldots,A_N,C_1,\ldots,C_N$ können die Ranglisten widerspruchsfrei gemacht werden.

Teilaufgaben

Teilaufgabe 1 [15 Punkte]

• $N \le 16$.

Teilaufgabe 2 [15 Punkte]

• $N \le 50$.

Teilaufgabe 3 [30 Punkte]

• $N \le 5000$.

Teilaufgabe 4 [40 Punkte]

Es gibt keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 1

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

Ausgabe 1

1

Hinweis

Ändert man $C_3$ zu $2$, erhält man folgende widerspruchsfreie Ranglisten:

• Der Teilnehmer aus Land $3$, der zwei Stunden nach Wettbewerbsbeginn mit $500$ Punkten auf Platz $1$ lag, beendete den Wettbewerb mit $700$ Punkten auf Platz $2$.
• Der Teilnehmer aus Land $2$, der zwei Stunden nach Wettbewerbsbeginn mit $200$ Punkten auf Platz $2$ lag, beendete den Wettbewerb mit $400$ Punkten auf Platz $3$.
• Der Teilnehmer aus Land $1$, der zwei Stunden nach Wettbewerbsbeginn mit $100$ Punkten auf Platz $3$ lag, beendete den Wettbewerb mit $1000$ Punkten auf Platz $1$.

Würde man stattdessen $C_2$ zu $2$ ändern, wären die Ranglisten widersprüchlich: Der Teilnehmer aus Land $3$ hätte zwei Stunden nach Wettbewerbsbeginn bereits $500$ Punkte, am Ende aber nur $400$ Punkte.

Da es unmöglich ist, mit weniger als einer Änderung widerspruchsfreie Ranglisten zu erhalten, wird $1$ ausgegeben.

Eingabe 2

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

Ausgabe 2

0

Hinweis

Hier sind die Ranglisten bereits ohne Änderungen an den Herkunftsländern widerspruchsfrei. Beachte, dass es Teilnehmer geben kann, deren Punktzahl sich seit dem Zeitpunkt zwei Stunden nach Wettbewerbsbeginn nicht erhöht hat. Außerdem können mehrere Teilnehmer dasselbe Herkunftsland haben.

Eingabe 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

Ausgabe 3

3

Hinweis

In diesem Beispiel erhält man widerspruchsfreie Ranglisten, indem man $A_1$ zu $2$, $A_6$ zu $4$ und $C_1$ zu $4$ ändert.