← 返回题目列表

AtCoder · arc046_c

C. 组数据操作

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

問題文

高桥和青木计划了一次集体约会。 2 人 N 男人和 M 成功聚集女性。男士用 1 它们的编号最大为 N 适合女性 每个都分配有 1 它们的编号最大为 M 编号。策划者高桥和青木的目标是最大限度地增加通过这次团体约会结成情侣的数量。 在这里,什么是情侣? 1 一群男人和女人。还有,每个人 2 不得包含在多对夫妇中。 编号为

i (1≦i≦N) 的男子的年收入为 A_i 日元,年收入为 B_i 我想与收入超过 100 日元的女性成为情侣。 编号为 j (1≦j≦M) 的女士的年收入为 C_j 日元,年收入为 D_j 我想和收入超过 100 日元的男人成为情侣。

高桥和青木是 与编号为 i 的人一起 j 当编号为编号的女士的要求同时得到满足时,即 当满足 B_i≦C_j 和 D_j≦A_i 时, i 与第一个男人 有可能与第 j 个女人结为情侣。

你的任务是找出这次相亲最多可以组成多少对情侣。


入力

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

N M
A_1 B_1
A_2 B_2
:
A_N B_N
C_1 D_1
C_2 D_2
:
C_M D_M
  • 1 行中代表男性和女性的数量 2 整数 给出了 N,M (1≦N,M≦150,000) 。
  • 2 从线 N 行 i (1≦i≦N) 行中,i 代表编号为本人的年收入和对方要求的年收入。 2 整数 给出了 A_i,B_i (1≦A_i,B_i≦10^9) 用空格分隔。
  • 2+N 从线 M 行 j (1≦j≦M) 行中,j 代表编号为女方的年收入和对方要求的年收入。 2 整数 给出了 C_j,D_j (1≦C_j,D_j≦10^9) 用空格分隔。

部分点

针对此问题设置了部分分数。 如果所有满足

  • 任何 在 i,j (1≦i≦N,1≦j≦M) 中 如果正确答案是满足 B_i≦C_j 的数据集 30 点。

出力

本次相亲最多可结成情侣数 在 1 行输出。在输出末尾插入换行符。


入力例 1

3 3
3 5
2 4
4 5
3 1
6 2
5 3

出力例 1

2
  • 1 的人一起 2 女情侣, 2 的人一起 3 女性情侣数建立时,所形成的情侣数为最大。 1 可能的情侣数量是 2 。
  • 请注意,对于每个人来说,他们不得属于多对夫妇。
  • 这种情况不满足部分分数的附加约束,因为存在女性年收入小于男性要求的年收入的情况。 女人的

入力例 2

3 4
4 1
2 1
7 1
5 3
12 1
1 10
8 5

出力例 2

3
  • 1 的人一起 1 , 2 的人一起 2 , 3的人一起 4女号情侣生成时,生成的情侣数量为最大,数量为 3 。
  • 这种情况满足部分点相加约束。

入力例 3

5 1
1 1
1 1
1 1
1 1
1 1
1 1

出力例 3

1
  • 这种情况满足部分点相加约束。

入力例 4

1 1
1 1
1 2

出力例 4

0
  • 成功夫妇的数量是 请注意,它也可能是 0 。
  • 这种情况满足部分点相加约束。