Vào năm 21XX, lập trình thi đấu đã được công nhận rộng rãi là một môn thể thao trí tuệ và thường xuyên xuất hiện trên các phương tiện truyền thông như truyền hình và báo chí.

Bạn là phóng viên của tòa soạn JOI, phụ trách các bài báo về lập trình thi đấu.

Hôm qua, một cuộc thi lập trình quốc tế với $N$ thí sinh đã diễn ra. Để viết bài về cuộc thi này, bạn được cung cấp các thông tin sau.

• Giống như Olympic Tin học Quốc tế, cuộc thi có thí sinh đến từ nhiều quốc gia. Mỗi quốc gia được đánh số bằng một số từ $1$ đến $N$. Có thể có nhiều thí sinh đến từ cùng một quốc gia. Cũng có thể có quốc gia không có thí sinh tham dự.
• Thời gian thi là 5 giờ.
• Điểm số mà thí sinh đã giành được trong cuộc thi không bao giờ bị giảm đi sau đó.
• Tại thời điểm 2 giờ sau khi bắt đầu cuộc thi, không có hai thí sinh nào bằng điểm nhau. Trong bảng xếp hạng lúc đó, thí sinh đứng thứ $i$ ($1\le i\le N$) đến từ quốc gia $A_i$ và có $B_i$ điểm.
• Khi cuộc thi kết thúc, không có hai thí sinh nào bằng điểm nhau. Trong bảng xếp hạng cuối cùng, thí sinh đứng thứ $i$ ($1\le i\le N$) đến từ quốc gia $C_i$ và có $D_i$ điểm.

Tuy nhiên, khi bạn chuẩn bị viết bài, người ta phát hiện có lỗi trong việc hiển thị quốc gia của thí sinh trên bảng xếp hạng. Thông tin quốc gia có thể đã bị hiển thị sai. Điểm số được hiển thị của các thí sinh được biết là chính xác.

Vì vậy, bạn quyết định suy đoán thông tin bảng xếp hạng nhất quán bằng cách sửa càng ít thông tin đã cho càng tốt (sao cho quốc gia của cùng một thí sinh không thay đổi trong cuộc thi và điểm của thí sinh không giảm trong cuộc thi). Cụ thể, bạn muốn thay đổi ít vị trí nhất trong $2N$ giá trị $A_1,\ldots,A_N,C_1,\ldots,C_N$ để thỏa mãn điều kiện sau:

• Tồn tại một hoán vị $x_1,x_2,\ldots,x_N$ của $1,2,\ldots,N$ sao cho với mỗi $i=1,2,\ldots,N$, ta có $A_i=C_{x_i}$ và $B_i\le D_{x_i}$.

Bạn cần sửa ít nhất bao nhiêu vị trí trong thông tin đã cho?

Nhiệm vụ

Cho số thí sinh dự thi cùng thông tin bảng xếp hạng tại thời điểm 2 giờ sau khi bắt đầu và khi kết thúc cuộc thi, hãy viết chương trình tính số vị trí thông tin quốc gia ít nhất cần thay đổi để các bảng xếp hạng trở nên nhất quán.

Dữ liệu vào

Đọc dữ liệu sau từ đầu vào chuẩn.

• Dòng đầu tiên chứa số nguyên $N$, cho biết có $N$ thí sinh tham gia cuộc thi.
• Dòng thứ $i$ ($1\le i\le N$) trong $N$ dòng tiếp theo chứa hai số nguyên $A_i,B_i$ cách nhau bởi dấu cách. Điều này có nghĩa trong bảng xếp hạng tại thời điểm 2 giờ sau khi bắt đầu cuộc thi, thí sinh đứng thứ $i$ được hiển thị là đến từ quốc gia $A_i$ và có $B_i$ điểm.
• Dòng thứ $i$ ($1\le i\le N$) trong $N$ dòng tiếp theo chứa hai số nguyên $C_i,D_i$ cách nhau bởi dấu cách. Điều này có nghĩa trong bảng xếp hạng cuối cùng, thí sinh đứng thứ $i$ được hiển thị là đến từ quốc gia $C_i$ và có $D_i$ điểm.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa số vị trí thông tin quốc gia ít nhất cần thay đổi để các bảng xếp hạng trở nên nhất quán.

Giới hạn

Tất cả dữ liệu vào thỏa mãn các điều kiện sau.

• $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$).
• Có thể làm cho các bảng xếp hạng trở nên nhất quán bằng cách thay đổi một số vị trí trong $A_1,\ldots,A_N,C_1,\ldots,C_N$.

Nhiệm vụ con

Nhiệm vụ con 1 [15 điểm]

• $N\le 16$.

Nhiệm vụ con 2 [15 điểm]

• $N\le 50$.

Nhiệm vụ con 3 [30 điểm]

• $N\le 5000$.

Nhiệm vụ con 4 [40 điểm]

Không có giới hạn bổ sung.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

1

Ghi chú

Nếu sửa giá trị $C_3$ thành $2$, các bảng xếp hạng sẽ nhất quán như sau:

• Thí sinh đến từ quốc gia $3$, đứng thứ nhất với $500$ điểm tại thời điểm 2 giờ sau khi bắt đầu cuộc thi, kết thúc cuộc thi ở vị trí thứ hai với $700$ điểm.
• Thí sinh đến từ quốc gia $2$, đứng thứ hai với $200$ điểm tại thời điểm 2 giờ sau khi bắt đầu cuộc thi, kết thúc cuộc thi ở vị trí thứ ba với $400$ điểm.
• Thí sinh đến từ quốc gia $1$, đứng thứ ba với $100$ điểm tại thời điểm 2 giờ sau khi bắt đầu cuộc thi, kết thúc cuộc thi ở vị trí thứ nhất với $1000$ điểm.

Nếu thay vào đó sửa $C_2$ thành $2$, bảng xếp hạng sẽ mâu thuẫn vì thí sinh đến từ quốc gia $3$ đã có $500$ điểm tại thời điểm 2 giờ sau khi bắt đầu cuộc thi nhưng khi kết thúc lại chỉ có $400$ điểm.

Không thể có bảng xếp hạng nhất quán bằng cách sửa ít hơn 1 vị trí, nên ghi ra $1$.

Dữ liệu vào 2

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

Dữ liệu ra 2

0

Ghi chú

Trong trường hợp này, các bảng xếp hạng đã nhất quán mà không cần sửa thông tin quốc gia. Lưu ý rằng có thể có thí sinh không tăng điểm so với thời điểm 2 giờ sau khi bắt đầu cuộc thi. Cũng lưu ý rằng bảng xếp hạng có thể có nhiều thí sinh đến từ cùng một quốc gia.

Dữ liệu vào 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

Dữ liệu ra 3

3

Ghi chú

Trong ví dụ này, sửa $A_1$ thành $2$, $A_6$ thành $4$ và $C_1$ thành $4$ sẽ làm cho các bảng xếp hạng nhất quán.