题目描述

当时是 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, \dots, A_N, C_1, \dots, C_N$ 中尽可能少的位置，使得以下条件成立：

• 存在一个 $1, 2, \dots, N$ 的排列 $x_1, x_2, \dots, x_N$，使得对每个 $i = 1, 2, \dots, N$，均有 $A_i = C_{x_i}$ 且 $B_i \le D_{x_i}$。

你被要求，根据所给信息，计算至少需要修改多少个位置。

题目

给定参赛选手数量、比赛开始 2 小时后的排名表与比赛结束时的排名表信息，编写一个程序，求出使排名表信息无矛盾所需的最少出身国信息修改位置数。

输入格式

从标准输入读取以下数据：

• 第 1 行包含一个整数 $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$。

输出格式

向标准输出输出一行，包含一个整数，表示为使排名表无矛盾所需的最少出身国信息修改位置数。

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

 1

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

0

 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

提示

数据范围

所有输入数据均满足以下条件：

• $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 分]

无额外限制。

翻译由 Qwen3-235B 完成