On vuosi 21XX, ja kilpaohjelmointi on laajalti tunnustettu älyurheilulajiksi, jota esitellään usein televisiossa ja sanomalehdissä. Olet JOI-uutistoimiston toimittaja, joka vastaa kilpaohjelmointia käsittelevistä artikkeleista. Eilen järjestettiin kansainvälinen kilpaohjelmointikilpailu, jossa oli $N$ osallistujaa. Kirjoittaaksesi artikkelin tästä kilpailusta sinulle on annettu seuraavat tiedot:

• Kuten kansainvälisissä tietotekniikkaolympialaisissa ja vastaavissa tapahtumissa, tämän kilpailun osallistujat tulivat useista maista. Maat on numeroitu 1:stä $N$:ään. Samasta maasta voi tulla useita osallistujia. Lisäksi voi olla maita, joista ei tullut yhtään osallistujaa.
• Tämän kilpailun kesto on 5 tuntia.
• Osallistujien kilpailun aikana saamat pisteet eivät koskaan vähene.
• Kaksi tuntia kilpailun alkamisen jälkeen kenelläkään osallistujista ei ollut samaa pistemäärää. Tuon hetken tulostaulussa $i$-nnellä sijalla ($1 \le i \le N$) ollut osallistuja oli maasta $A_i$ ja hänen pistemääränsä oli $B_i$.
• Kilpailun päättyessä kenelläkään osallistujista ei ollut samaa pistemäärää. Kilpailun lopun tulostaulussa $i$-nnellä sijalla ($1 \le i \le N$) ollut osallistuja oli maasta $C_i$ ja hänen pistemääränsä oli $D_i$.

Artikkelin kirjoitusvaiheessa kuitenkin huomattiin, että tulostaulujen lähtömaiden esittämisessä oli virhe. On mahdollista, että osallistujien lähtömaita koskevat tiedot näytettiin väärin. Tiedetään, että osallistujien näytetyt pistemäärät ovat oikein.

Niinpä päätit päätellä ristiriidattoman tulostaulun (jossa saman osallistujan lähtömaa ei muutu kilpailun aikana eikä osallistujan saama pistemäärä vähene kilpailun aikana) tekemällä mahdollisimman vähän korjauksia annettuihin tietoihin. Toisin sanoen haluat täyttää seuraavan ehdon muuttamalla mahdollisimman harvaa $2N$ arvosta $A_1, \dots, A_N, C_1, \dots, C_N$:

• Lukujen $1, 2, \dots, N$ joukolle on olemassa permutaatio $x_1, x_2, \dots, x_N$, jolle jokaisella $i = 1, 2, \dots, N$ pätee $A_i = C_{x_i}$ ja $B_i \le D_{x_i}$.

Kuinka monta korjausta annettuihin tietoihin on vähintään tehtävä?

Syöte

Lue seuraavat tiedot vakiosyötteestä:

• Ensimmäinen rivi sisältää kokonaisluvun $N$, joka ilmaisee kilpailun osallistujien lukumäärän.
• Seuraavien $N$ rivin $i$-s rivi ($1 \le i \le N$) sisältää välilyönnillä erotetut kokonaisluvut $A_i$ ja $B_i$. Tämä osoittaa, että 2 tuntia kilpailun alkamisen jälkeen tulostaulussa $i$-nnellä sijalla ollut osallistuja oli maasta $A_i$ ja hänen pistemääränsä oli $B_i$.
• Sitä seuraavien $N$ rivin $i$-s rivi ($1 \le i \le N$) sisältää välilyönnillä erotetut kokonaisluvut $C_i$ ja $D_i$. Tämä osoittaa, että kilpailun lopun tulostaulussa $i$-nnellä sijalla ollut osallistuja oli maasta $C_i$ ja hänen pistemääränsä oli $D_i$.

Tuloste

Tulosta yhdelle riville pienin määrä lähtömaatietoihin tehtäviä korjauksia, joka tarvitaan tekemään tulostaulusta ristiriidaton.

Rajoitukset

Kaikki syötetiedot täyttävät seuraavat ehdot:

• $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$).
• Tulostaulusta on mahdollista tehdä ristiriidaton muuttamalla joitakin arvoista $A_1, \dots, A_N, C_1, \dots, C_N$.

Osatehtävät

1. (15 pistettä) $N \le 16$ täyttyy.
2. (15 pistettä) $N \le 50$ täyttyy.
3. (30 pistettä) $N \le 5000$ täyttyy.
4. (40 pistettä) Ei lisärajoituksia.

Esimerkit

Syöte 1

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

Tuloste 1

1

Huomautus 1

Jos muutat luvun $C_3$ arvoksi 2, tulostaulusta tulee ristiriidaton seuraavasti:

• Maasta 3 tuleva osallistuja, joka oli 1. sijalla 500 pisteellä 2 tuntia aloituksen jälkeen, sijoittui lopulta 2. sijalle 700 pisteellä.
• Maasta 2 tuleva osallistuja, joka oli 2. sijalla 200 pisteellä 2 tuntia aloituksen jälkeen, sijoittui lopulta 3. sijalle 400 pisteellä.
• Maasta 1 tuleva osallistuja, joka oli 3. sijalla 100 pisteellä 2 tuntia aloituksen jälkeen, sijoittui lopulta 1. sijalle 1000 pisteellä.

Jos tässä muutat luvun $C_2$ arvoksi 2, maasta 3 tulevalla osallistujalla on 500 pistettä 2 tuntia aloituksen jälkeen, mutta kilpailun lopussa hänellä on 400 pistettä, mikä johtaa ristiriitaiseen tulostauluun. Koska ristiriidatonta tulostaulua on mahdotonta saada alle 1 korjauksella, tulosta 1.

Syöte 2

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

Tuloste 2

0

Huomautus 2

Tässä tapauksessa tulostaulu on ristiriidaton muuttamatta lähtömaatietoja. Huomaa, että mukana voi olla osallistujia, joiden pistemäärä ei kasvanut siitä pistemäärästä, joka heillä oli 2 tuntia kilpailun alkamisen jälkeen. Huomaa myös, että tulostaulussa voi olla useita osallistujia samasta maasta.

Syöte 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

Tuloste 3

3

Huomautus 3

Tässä esimerkissä, jos muutat luvun $A_1$ arvoksi 2, luvun $A_6$ arvoksi 4 ja luvun $C_1$ arvoksi 4, tulostaulusta tulee ristiriidaton.