Árið er 21XX og keppnisforritun er víða viðurkennd sem hugaríþrótt og birtist oft í fjölmiðlum eins og sjónvarpi og dagblöðum. Þú ert blaðamaður hjá JOI-fréttastofunni og sérð um greinar um keppnisforritun. Í gær var haldin alþjóðleg keppni í keppnisforritun með $N$ þátttakendum. Til að skrifa grein um þessa keppni hefur þú fengið eftirfarandi upplýsingar:

• Eins og á Alþjóðaólympíuleikunum í upplýsingatækni og svipuðum viðburðum komu þátttakendur í þessari keppni frá nokkrum löndum. Löndin eru númeruð frá 1 til $N$. Margir þátttakendur geta komið frá sama landinu. Einnig geta verið lönd sem engir þátttakendur komu frá.
• Lengd þessarar keppni er 5 klukkustundir.
• Stigin sem þátttakendur fá á meðan á keppninni stendur lækka aldrei.
• Tveimur klukkustundum eftir að keppnin hófst voru engir þátttakendur með jafnmörg stig. Á stigatöflunni á þeim tíma var þátttakandinn í $i$-ta sæti ($1 \le i \le N$) frá landi $A_i$ og var með $B_i$ stig.
• Í lok keppninnar voru engir þátttakendur með jafnmörg stig. Á stigatöflunni í lok keppninnar var þátttakandinn í $i$-ta sæti ($1 \le i \le N$) frá landi $C_i$ og var með $D_i$ stig.

Hins vegar, þegar kom að því að skrifa greinina, uppgötvaðist að galli var á birtingu upprunalanda á stigatöflunum. Mögulegt er að upplýsingarnar um upprunalönd þátttakenda hafi birst rangt. Vitað er að birt stig þátttakendanna eru rétt.

Þess vegna ákvaðst þú að leiða út samræmda stigatöflu (þar sem upprunaland sama þátttakanda breytist ekki á meðan á keppninni stendur, og stigin sem þátttakandi fær lækka ekki á meðan á keppninni stendur) með því að gera eins fáar leiðréttingar og mögulegt er á gefnum upplýsingum. Það er að segja, þú vilt uppfylla eftirfarandi skilyrði með því að breyta eins fáum og mögulegt er af hinum $2N$ gildum $A_1, \dots, A_N, C_1, \dots, C_N$:

• Til er umröðun $x_1, x_2, \dots, x_N$ á $1, 2, \dots, N$ þannig að fyrir hvert $i = 1, 2, \dots, N$ gildir að $A_i = C_{x_i}$ og $B_i \le D_{x_i}$.

Hversu margar leiðréttingar, að lágmarki, þarftu að gera á gefnum upplýsingum?

Inntak

Lesið eftirfarandi gögn úr staðalinntaki:

• Fyrsta línan inniheldur heiltölu $N$, sem táknar fjölda þátttakenda í keppninni.
• $i$-ta línan af næstu $N$ línum ($1 \le i \le N$) inniheldur heiltölurnar $A_i$ og $B_i$ aðskildar með bili. Þetta gefur til kynna að á stigatöflunni 2 klukkustundum eftir upphaf keppninnar hafi þátttakandinn í $i$-ta sæti verið frá landi $A_i$ og haft $B_i$ stig.
• $i$-ta línan af næstu $N$ línum þar á eftir ($1 \le i \le N$) inniheldur heiltölurnar $C_i$ og $D_i$ aðskildar með bili. Þetta gefur til kynna að á stigatöflunni í lok keppninnar hafi þátttakandinn í $i$-ta sæti verið frá landi $C_i$ og haft $D_i$ stig.

Úttak

Skrifið út á einni línu lágmarksfjölda leiðréttinga á upplýsingum um upprunaland sem þarf til að gera stigatöfluna samræmda.

Takmarkanir

Öll inntaksgögn uppfylla eftirfarandi skilyrði:

• $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$).
• Hægt er að gera stigatöfluna samræmda með því að breyta nokkrum gildum af $A_1, \dots, A_N, C_1, \dots, C_N$.

Undirverkefni

1. (15 stig) $N \le 16$ er uppfyllt.
2. (15 stig) $N \le 50$ er uppfyllt.
3. (30 stig) $N \le 5000$ er uppfyllt.
4. (40 stig) Engar frekari takmarkanir.

Dæmi

Inntak 1

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

Úttak 1

1

Athugasemd 1

Ef þú breytir gildinu á $C_3$ í 2 verður stigataflan samræmd á eftirfarandi hátt:

• Þátttakandinn frá landi 3, sem var í 1. sæti með 500 stig 2 klukkustundum eftir byrjun, endaði í 2. sæti með 700 stig.
• Þátttakandinn frá landi 2, sem var í 2. sæti með 200 stig 2 klukkustundum eftir byrjun, endaði í 3. sæti með 400 stig.
• Þátttakandinn frá landi 1, sem var í 3. sæti með 100 stig 2 klukkustundum eftir byrjun, endaði í 1. sæti með 1000 stig.

Hér, ef þú breytir gildinu á $C_2$ í 2, er þátttakandinn frá landi 3 með 500 stig 2 klukkustundum eftir byrjun, en með 400 stig í lok keppninnar, sem leiðir til ósamræmdrar stigatöflu. Þar sem ómögulegt er að fá samræmda stigatöflu með færri en 1 leiðréttingu skal skrifa út 1.

Inntak 2

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

Úttak 2

0

Athugasemd 2

Í þessu tilviki er stigataflan samræmd án þess að breyta upplýsingum um upprunaland. Athugið að það geta verið þátttakendur sem hækkuðu ekki stigin sín frá stigunum 2 klukkustundum eftir upphaf keppninnar. Athugið einnig að það geta verið margir þátttakendur frá sama landi á stigatöflunni.

Inntak 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

Úttak 3

3

Athugasemd 3

Í þessu dæmi, ef þú breytir gildinu á $A_1$ í 2, gildinu á $A_6$ í 4 og gildinu á $C_1$ í 4, verður stigataflan samræmd.