ในปี 21XX การแข่งขันเขียนโปรแกรมได้รับการยอมรับอย่างแพร่หลายว่าเป็นกีฬาทางปัญญาประเภทหนึ่ง และมักถูกนำเสนอผ่านสื่อต่าง ๆ เช่น โทรทัศน์และหนังสือพิมพ์

คุณเป็นผู้สื่อข่าวของสำนักหนังสือพิมพ์ JOI รับผิดชอบบทความเกี่ยวกับการแข่งขันเขียนโปรแกรม

เมื่อวานมีการแข่งขันเขียนโปรแกรมระดับนานาชาติที่มีผู้เข้าแข่งขัน $N$ คน คุณได้รับข้อมูลต่อไปนี้เพื่อเขียนบทความเกี่ยวกับการแข่งขันนี้

• เช่นเดียวกับโอลิมปิกคอมพิวเตอร์ระหว่างประเทศ ผู้เข้าแข่งขันในการแข่งขันนี้มาจากหลายประเทศ แต่ละประเทศมีหมายเลขหนึ่งหมายเลขจาก $1$ ถึง $N$ ประเทศหนึ่งอาจมีผู้เข้าแข่งขันหลายคน และบางประเทศอาจไม่มีผู้เข้าแข่งขันเลย
• การแข่งขันนี้ใช้เวลา 5 ชั่วโมง
• คะแนนที่ผู้เข้าแข่งขันได้รับระหว่างการแข่งขันจะไม่มีการลดลงในภายหลัง
• เมื่อผ่านไป 2 ชั่วโมงหลังเริ่มการแข่งขัน ไม่มีผู้เข้าแข่งขันคนใดมีคะแนนเท่ากัน ในตารางอันดับ ณ เวลานั้น ผู้เข้าแข่งขันอันดับที่ $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}$

คุณจำเป็นต้องแก้ไขข้อมูลที่ได้รับอย่างน้อยกี่ตำแหน่ง?

งานที่ต้องทำ

เมื่อได้รับจำนวนผู้เข้าแข่งขันและข้อมูลตารางอันดับเมื่อผ่านไป 2 ชั่วโมงหลังเริ่มการแข่งขันกับเมื่อสิ้นสุดการแข่งขัน จงเขียนโปรแกรมหาจำนวนตำแหน่งข้อมูลประเทศที่ต้องเปลี่ยนให้น้อยที่สุด เพื่อให้ตารางอันดับสอดคล้องกัน

ข้อมูลนำเข้า

อ่านข้อมูลต่อไปนี้จากข้อมูลนำเข้ามาตรฐาน

• บรรทัดแรกมีจำนวนเต็ม $N$ ซึ่งหมายความว่ามีผู้เข้าแข่งขัน $N$ คน
• บรรทัดที่ $i$ ($1 \le i \le N$) ของ $N$ บรรทัดถัดมามีจำนวนเต็ม $A_i,B_i$ คั่นด้วยช่องว่าง หมายความว่าในตารางอันดับเมื่อผ่านไป 2 ชั่วโมงหลังเริ่มการแข่งขัน ผู้เข้าแข่งขันอันดับที่ $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 ซึ่งอยู่อันดับ 1 ด้วยคะแนน 500 เมื่อผ่านไป 2 ชั่วโมงหลังเริ่มการแข่งขัน จบการแข่งขันที่อันดับ 2 ด้วยคะแนน 700
• ผู้เข้าแข่งขันจากประเทศ 2 ซึ่งอยู่อันดับ 2 ด้วยคะแนน 200 เมื่อผ่านไป 2 ชั่วโมงหลังเริ่มการแข่งขัน จบการแข่งขันที่อันดับ 3 ด้วยคะแนน 400
• ผู้เข้าแข่งขันจากประเทศ 1 ซึ่งอยู่อันดับ 3 ด้วยคะแนน 100 เมื่อผ่านไป 2 ชั่วโมงหลังเริ่มการแข่งขัน จบการแข่งขันที่อันดับ 1 ด้วยคะแนน 1000

ในทางกลับกัน หากแก้ค่า $C_2$ เป็น $2$ ตารางอันดับจะขัดแย้งกัน เพราะผู้เข้าแข่งขันจากประเทศ 3 ได้ 500 คะแนนเมื่อผ่านไป 2 ชั่วโมงหลังเริ่มการแข่งขัน แต่กลับมี 400 คะแนนเมื่อสิ้นสุดการแข่งขัน

ไม่สามารถทำให้ตารางอันดับสอดคล้องกันด้วยการแก้ไขน้อยกว่า 1 ตำแหน่งได้ จึงพิมพ์ 1

ข้อมูลนำเข้า 2

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

ข้อมูลส่งออก 2

0

หมายเหตุ

ในกรณีนี้ ตารางอันดับสอดคล้องกันอยู่แล้วโดยไม่ต้องแก้ข้อมูลประเทศ โปรดสังเกตว่าอาจมีผู้เข้าแข่งขันที่คะแนนไม่เพิ่มจากคะแนนเมื่อผ่านไป 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

หมายเหตุ

ในตัวอย่างนี้ หากแก้ค่า $A_1$ เป็น $2$ แก้ค่า $A_6$ เป็น $4$ และแก้ค่า $C_1$ เป็น $4$ จะได้ตารางอันดับที่สอดคล้องกัน