AT_joig2026final_k お菓子詰め (Packing Snacks)

葵平时喜欢做糕点，经常会把自己制作的糕点分发给他人。葵答应在 JOI 纪念日送糕点给比太郎。 当天，葵制作了 $N$ 个糕点。每个糕点有一种类型和一个大小，类型用 $1$ 到 $T$ 之间的整数表示。这些糕点编号为 $1$ 到 $N$。第 $i$ 个糕点（$1 \leq i \leq N$）的类型为 $A_i$，大小为 $C_i$。葵会在这 $N$ 个糕点中，选出恰好 $M$ 个带到比太郎家，其中 $1 \leq M \leq N$。 比太郎有 $M$ 个袋子，袋子编号为 $1$ 到 $M$。第 $j$ 个袋子（$1 \leq j \leq M$）只能放类型为 $B_j$ 且大小不超过 $D_j$ 的糕点，且每个袋子最多只能放一个糕点。比太郎会把葵带来的 $M$ 个糕点中，能放进袋子的所有糕点都拿走。 比太郎想拿到尽可能多的糕点，会合理分配带来的糕点放到袋子里。另一方面，葵还想把糕点分一些给其他人，所以会选择让比太郎能拿到的糕点数尽量少的方案，并且她已经知道比太郎袋子的信息。 给定糕点和袋子的相关信息，编写程序计算比太郎最终能得到的糕点数。 ---

输入从标准输入获得，格式如下： > $N\ M\ T$ > $A_1\ C_1$ > $A_2\ C_2$ > $\vdots$ > $A_N\ C_N$ > $B_1\ D_1$ > $B_2\ D_2$ > $\vdots$ > $B_M\ D_M$ ---

输出比太郎能拿到的糕点数，输出一行。 ---

### 子任务 1. ($12$ 分) $T = 1$。 2. ($17$ 分) $N \leq 10$。 3. ($9$ 分) $N = M = T$，并且 $A_i = B_i = i \ (1 \leq i \leq N)$。 4. ($36$ 分) $N \leq 5\,000$。 5. ($26$ 分) 没有额外限制。 --- ### 样例解释 1 若葵带着第 $1, 3, 5$ 号糕点去比太郎家时，比太郎能拿到的糕点最少。在这种情况下，比太郎可以如下分配，把最多 $2$ 个糕点放入袋子并拿到： - 把糕点 $1$ 放进袋子 $1$。 - 把糕点 $5$ 放进袋子 $2$。 在任何情况下，葵都不能让比太郎拿到比 $2$ 更少的糕点，因此应输出 $2$。 该输入样例符合子任务 $1, 2, 4, 5$ 的限制。 --- ### 样例解释 2 若葵带着第 $1, 4, 5$ 号糕点去比太郎家时，比太郎能拿到的糕点最少。在这种情况下，比太郎可以如下分配，把最多 $1$ 个糕点放入袋子并拿到： - 把糕点 $1$ 放进袋子 $1$。 在任何情况下，葵都不能让比太郎拿到比 $1$ 更少的糕点，因此应输出 $1$。 该输入样例符合子任务 $2, 4, 5$ 的限制。 --- ### 样例解释 3 该输入样例符合子任务 $2, 3, 4, 5$ 的限制。 --- ### 样例解释 4 该输入样例符合子任务 $2, 4, 5$ 的限制。 # 数据范围与限制 - $1 \leq N \leq 500\,000$。 - $1 \leq M \leq \min(N, 5\,000)$。 - $1 \leq T \leq N$。 - $1 \leq A_i \leq T \quad (1 \leq i \leq N)$。 - $1 \leq C_i \leq 10^9 \quad (1 \leq i \leq N)$。 - $1 \leq B_j \leq T \quad (1 \leq j \leq M)$。 - $1 \leq D_j \leq 10^9 \quad (1 \leq j \leq M)$。 - 输入的所有值均为整数。 由 ChatGPT 5 翻译