نحن في عام 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,\ldots,A_N,C_1,\ldots,C_N$ حتى يتحقق الشرط التالي:

• توجد إعادة ترتيب $x_1,x_2,\ldots,x_N$ للأعداد $1,2,\ldots,N$ بحيث لكل $i=1,2,\ldots,N$ يتحقق $A_i=C_{x_i}$ و$B_i\le D_{x_i}$.

ما أقل عدد من المواضع التي تحتاج إلى تعديلها في المعلومات المعطاة؟

المهمة

اكتب برنامجًا يُعطى عدد المشاركين ومعلومات لوحة الترتيب بعد ساعتين من بداية المسابقة وعند نهايتها، ويحسب أقل عدد من مواضع معلومات الدول التي يجب تغييرها لجعل لوحتَي الترتيب متسقتين.

الإدخال

اقرأ البيانات التالية من الإدخال القياسي.

• يحتوي السطر الأول على عدد صحيح $N$، وهو عدد المتسابقين المشاركين.
• يحتوي السطر رقم $i$ ($1\le i\le N$) من الأسطر $N$ التالية على عددين صحيحين $A_i,B_i$ يفصل بينهما فراغ. يعني ذلك أن المتسابق في المركز $i$ بعد ساعتين من بداية المسابقة عُرض على أنه من الدولة $A_i$، وكانت نقاطه $B_i$.
• يحتوي السطر رقم $i$ ($1\le i\le N$) من الأسطر $N$ التالية على عددين صحيحين $C_i,D_i$ يفصل بينهما فراغ. يعني ذلك أن المتسابق في المركز $i$ عند نهاية المسابقة عُرض على أنه من الدولة $C_i$، وكانت نقاطه $D_i$.

الإخراج

اطبع في سطر واحد من الإخراج القياسي أقل عدد من مواضع معلومات الدول التي يجب تغييرها لجعل لوحتَي الترتيب متسقتين.

القيود

تحقق جميع بيانات الإدخال الشروط التالية.

• $2\le N\le200\,000$.
• $1\le A_i\le N$ ($1\le i\le N$).
• $0\le B_i\le1\,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\le1\,000\,000\,000$ ($1\le i\le N$).
• $D_i>D_{i+1}$ ($1\le i\le N-1$).
• يمكن جعل لوحتَي الترتيب متسقتين بتغيير بعض القيم $A_1,\ldots,A_N,C_1,\ldots,C_N$.

المهام الفرعية

المهمة الفرعية 1 [15 نقطة]

• يتحقق $N\le16$.

المهمة الفرعية 2 [15 نقطة]

• يتحقق $N\le50$.

المهمة الفرعية 3 [30 نقطة]

• يتحقق $N\le5000$.

المهمة الفرعية 4 [40 نقطة]

لا توجد قيود إضافية.

أمثلة

الإدخال 1

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

الإخراج 1

1

ملاحظة

إذا عُدلت قيمة $C_3$ إلى $2$، تصبح لوحتا الترتيب متسقتين كما يلي:

• المتسابق من الدولة $3$، الذي كان في المركز الأول برصيد $500$ نقطة بعد ساعتين من البداية، أصبح في المركز الثاني برصيد $700$ نقطة عند نهاية المسابقة.
• المتسابق من الدولة $2$، الذي كان في المركز الثاني برصيد $200$ نقطة بعد ساعتين من البداية، أصبح في المركز الثالث برصيد $400$ نقطة عند نهاية المسابقة.
• المتسابق من الدولة $1$، الذي كان في المركز الثالث برصيد $100$ نقطة بعد ساعتين من البداية، أصبح في المركز الأول برصيد $1000$ نقطة عند نهاية المسابقة.

أما إذا عُدلت قيمة $C_2$ إلى $2$، فسيكون المتسابق من الدولة $3$ قد حصل على $500$ نقطة بعد ساعتين من البداية، لكن رصيده في النهاية سيكون $400$ نقطة، فتكون لوحتا الترتيب غير متسقتين.

يستحيل الحصول على لوحتَي ترتيب متسقتين بأقل من تعديل واحد، لذا نطبع 1.

الإدخال 2

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

الإخراج 2

0

ملاحظة

في هذه الحالة، لوحتا الترتيب متسقتان دون تعديل معلومات الدول. لاحظ أنه قد يوجد متسابقون لم تزد نقاطهم منذ مرور ساعتين على بداية المسابقة. ولاحظ أيضًا أنه قد يظهر عدة متسابقين من الدولة نفسها في لوحة الترتيب.

الإدخال 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

ملاحظة

في هذا المثال، تصبح لوحتا الترتيب متسقتين إذا عُدلت قيمة $A_1$ إلى $2$، وقيمة $A_6$ إلى $4$، وقيمة $C_1$ إلى $4$.