← 返回题目列表

AtCoder · joig2026final_k

K. 包装零食

中文机器翻译题面 查看原题

配点 : 100 点

問題文

葵的爱好是制作糖果,她经常把糖果送给别人。 葵答应在 JOI 周年纪念日送给 Bitaro 一些糖果。

那天,葵 我做了 N 糖果。 糖果有不同的种类和大小,其种类有 1 以上 T 由以下整数表示。 还有这些甜点 它们的编号最大为 1 如果要将其更改为输出最多为 N 。 糖果 i (1 \leqq i \leqq N) 的类型是 A_i 尺寸为 C_i 。 葵是 N 糖果,正是 选择 M 糖果并将它们带到Bitaro的家。 这里 它是小于或等于 M 是 1 以上 N 的整数。

比特太郎是 我有 M 袋子,袋子里装有 它们的编号最大为 1 如果要将其更改为输出最多为 M 。 包 j (1 \leqq j \leqq M)具有类型 B_j 尺寸为 D_j 最大糖果数量如下 可以插入 1 。 葵带来了比特太郎。 获取所有可以装入袋子的 M 糖果。

比特太郎想要收到尽可能多的糖果,所以他把带来的糖果放进袋子里,这样他就能收到尽可能多的糖果。 另一方面,葵想向其他人分发糖果,因此她选择要带的糖果,以便Bitaro收到尽可能少的糖果。 然而,葵知道比特太郎所携带的包的信息。

给定有关糖果和袋子的信息,编写一个程序来计算 Bitaro 可以收到的糖果数量。


入力

输入是按以下格式从标准输入给出的。

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

出力

Bitaro 可以接收的糖果数量被写入标准输出。 1 行。


制約

  • 1 \leqq N \leqq 500\,000.
  • 1 \leqq M \leqq \min(N,5\,000).
  • 1 \leqq T \leqq N.
  • 1 \leqq A_i \leqq T (1 \leqq i \leqq N).
  • 1 \leqq C_i \leqq 10^9 (1 \leqq i \leqq N).
  • 1 \leqq B_j \leqq T (1 \leqq j \leqq M).
  • 1 \leqq D_j \leqq 10^9 (1 \leqq j \leqq M).
  • 所有输入值都是整数。

小課題

  1. (12 点) T = 1.
  2. (17 点) N \leqq 10.
  3. (9 点) N = M = T,A_i = B_i = i (1 \leqq i \leqq N).
  4. (36 点) N \leqq 5\,000.
  5. (26 点)没有额外的限制。

入力例 1

5 3 1
1 9
1 3
1 6
1 1
1 5
1 10
1 5
1 5

出力例 1

2

葵是糖果 如果你带上 1,3,5 ,Bitaro将收到最少数量的糖果。 此时,Bitaro 可以通过将糖果放入袋子中来最大限度地增加糖果数量,如下所示。 您可以获得 2 糖果。

  • 糖果 1 包 将其放入 1 。
  • 糖果 5 包 将其放入 2 。

葵计算Bitaro可以收到的最大糖果数量。 2 不能小于2 。

此输入示例是一个小作业。 1,2,4,5 满足约束。


入力例 2

5 3 3
1 9
2 3
2 6
3 1
3 5
1 10
2 7
2 5

出力例 2

1

葵是糖果 如果你带上 1,4,5 ,Bitaro将收到最少数量的糖果。 此时,Bitaro 可以通过将糖果放入袋子中来最大限度地增加糖果数量,如下所示。 您可以获得 1 糖果。

  • 糖果 1 包 将其放入 1 。

葵计算Bitaro可以收到的最大糖果数量。 1 不能小于1 。

此输入示例是一个小作业。 2,4,5 满足约束。


入力例 3

5 5 5
1 9
2 3
3 6
4 1
5 5
1 10
2 7
3 5
4 8
5 6

出力例 3

4

此输入示例是一个小作业。 2,3,4,5 满足约束。


入力例 4

3 3 2
1 5
1 5
1 1
1 2
1 2
2 2

出力例 4

1

此输入示例是一个小作业。 2,4,5 满足约束。