Қазір 21XX жыл, спорттық программалау зияткерлік спорт түрі ретінде кеңінен танылып, теледидар мен газет сияқты бұқаралық ақпарат құралдарында жиі көрсетіледі. Сіз JOI ақпарат агенттігінің спорттық программалау туралы мақалаларға жауапты тілшісісіз. Кеше $N$ қатысушы қатысқан халықаралық спорттық программалау жарысы өтті. Осы жарыс туралы мақала жазу үшін сізге келесі ақпарат берілді:

• Халықаралық информатика олимпиадасы мен оған ұқсас іс-шаралардағыдай, бұл жарысқа қатысушылар бірнеше елден келді. Елдер 1-ден $N$-ге дейін нөмірленген. Бір елден бірнеше қатысушы келуі мүмкін. Сондай-ақ бірде-бір қатысушы келмеген елдер де болуы мүмкін.
• Бұл жарыстың ұзақтығы — 5 сағат.
• Жарыс барысында қатысушылардың жинаған ұпайлары ешқашан кемімейді.
• Жарыс басталғаннан кейін екі сағат өткенде ұпайлары бірдей қатысушылар болған жоқ. Сол уақыттағы көшбасшылар тақтасында $i$-ші орындағы ($1 \le i \le N$) қатысушы $A_i$ елінен болды және оның ұпайы $B_i$ болды.
• Жарыс аяқталған кезде ұпайлары бірдей қатысушылар болған жоқ. Жарыс соңындағы көшбасшылар тақтасында $i$-ші орындағы ($1 \le i \le N$) қатысушы $C_i$ елінен болды және оның ұпайы $D_i$ болды.

Алайда мақала жазу кезеңінде көшбасшылар тақтасында қатысушылардың шыққан елдерін көрсетуде ақау болғаны анықталды. Қатысушылардың шыққан елдері туралы ақпарат қате көрсетілген болуы мүмкін. Қатысушылардың көрсетілген ұпайлары дұрыс екені белгілі.

Сондықтан сіз берілген ақпаратқа мүмкіндігінше аз түзету енгізу арқылы қайшылықсыз көшбасшылар тақтасын (жарыс барысында бір қатысушының елі өзгермейтін және қатысушының жинаған ұпайы кемімейтін көшбасшылар тақтасын) қалпына келтіруді ұйғардыңыз. Яғни, $2N$ мәндердің ($A_1, \dots, A_N, C_1, \dots, C_N$) мүмкіндігінше азын өзгерту арқылы келесі шартты қанағаттандырғыңыз келеді:

• Әрбір $i = 1, 2, \dots, N$ үшін $A_i = C_{x_i}$ және $B_i \le D_{x_i}$ орындалатындай $1, 2, \dots, N$ сандарының $x_1, x_2, \dots, x_N$ орын алмастыруы (пермутациясы) табылады.

Берілген ақпаратқа кем дегенде қанша түзету енгізуіңіз керек?

Кіріс деректер

Стандартты кірістен келесі деректерді оқыңыз:

• Бірінші жолда жарысқа қатысушылар санын білдіретін бір бүтін сан $N$ берілген.
• Келесі $N$ жолдың $i$-ші жолында ($1 \le i \le N$) бос орынмен бөлінген $A_i$ және $B_i$ бүтін сандары берілген. Бұл жарыс басталғаннан кейін 2 сағат өткендегі көшбасшылар тақтасында $i$-ші орындағы қатысушы $A_i$ елінен болғанын және ұпайы $B_i$ болғанын білдіреді.
• Одан кейінгі $N$ жолдың $i$-ші жолында ($1 \le i \le N$) бос орынмен бөлінген $C_i$ және $D_i$ бүтін сандары берілген. Бұл жарыс соңындағы көшбасшылар тақтасында $i$-ші орындағы қатысушы $C_i$ елінен болғанын және ұпайы $D_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$).
• $A_1, \dots, A_N, C_1, \dots, C_N$ мәндерінің кейбірін өзгерту арқылы көшбасшылар тақтасын қайшылықсыз етуге болады.

Ішкі тапсырмалар

1. (15 ұпай) $N \le 16$ шарты орындалады.
2. (15 ұпай) $N \le 50$ шарты орындалады.
3. (30 ұпай) $N \le 5000$ шарты орындалады.
4. (40 ұпай) Қосымша шектеулер жоқ.

Мысалдар

Кіріс 1

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

Шығыс 1

1

Ескертпе 1

Егер $C_3$ мәнін 2-ге өзгертсеңіз, көшбасшылар тақтасы келесідей қайшылықсыз болады:

• Басталғаннан кейін 2 сағат өткенде 500 ұпаймен 1-ші орында тұрған 3-елдің қатысушысы жарысты 700 ұпаймен 2-ші орында аяқтады.
• Басталғаннан кейін 2 сағат өткенде 200 ұпаймен 2-ші орында тұрған 2-елдің қатысушысы жарысты 400 ұпаймен 3-ші орында аяқтады.
• Басталғаннан кейін 2 сағат өткенде 100 ұпаймен 3-ші орында тұрған 1-елдің қатысушысы жарысты 1000 ұпаймен 1-ші орында аяқтады.

Мұнда егер $C_2$ мәнін 2-ге өзгертсеңіз, 3-елдің қатысушысында басталғаннан кейін 2 сағат өткенде 500 ұпай болса, жарыс соңында 400 ұпай болып, қайшылықты көшбасшылар тақтасы шығады. 1 түзетуден аз түзетумен қайшылықсыз көшбасшылар тақтасын алу мүмкін болмағандықтан, 1 шығарыңыз.

Кіріс 2

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

Шығыс 2

0

Ескертпе 2

Бұл жағдайда шыққан елі туралы ақпаратты өзгертпей-ақ көшбасшылар тақтасы қайшылықсыз болып тұр. Жарыс басталғаннан кейін 2 сағат өткендегі ұпайынан ұпайы өспеген қатысушылар болуы мүмкін екенін ескеріңіз. Сондай-ақ көшбасшылар тақтасында бір елден бірнеше қатысушы болуы мүмкін екенін ескеріңіз.

Кіріс 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

Шығыс 3

3

Ескертпе 3

Бұл мысалда $A_1$ мәнін 2-ге, $A_6$ мәнін 4-ке және $C_1$ мәнін 4-ке өзгертсеңіз, көшбасшылар тақтасы қайшылықсыз болады.