השנה היא 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$. משמעותו היא שבתחרות השתתפו $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 \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,\ldots,A_N,C_1,\ldots,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

הסבר

אם מתקנים את הערך $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$, מתקבלות טבלאות דירוג עקביות.