分数: 400 分
问题陈述
高桥和青木分别计划在 N \times N 网格公告板。公告板的每个单元格都用坐标表示 (r, c) (1 \leq r \leq N, 1 \leq c \leq N),其中 r 是从顶部开始计数的行号, c 是从左侧算起的列号。
高桥计划发布 A 矩形广告,青木计划张贴 B 布告栏上的矩形广告。每个广告覆盖由其左上角单元格指定的矩形区域 (r_1, c_1) 和右下单元格 (r_2, c_2)。也就是说,所有细胞 (r, c) 满意 r_1 \leq r \leq r_2 和 c_1 \leq c \leq c_2 已被覆盖。
公告板管理员担心高桥和青木的广告覆盖的单元格看起来不美观,因此想提前知道此类重叠单元格的总数。
找出至少一个高桥广告和至少一个青木广告覆盖的单元格数量。即使同一个小区被多种广告组合覆盖,也只算一次。
约束
- 1 \leq N \leq 500
- 1 \leq A \leq 100
- 1 \leq B \leq 100
- 对于高桥的每个广告 i (1 \leq i \leq A): 1 \leq r_{1,i} \leq r_{2,i} \leq N, 1 \leq c_{1,i} \leq c_{2,i} \leq N
- 对于青木的每个广告 j (1 \leq j \leq B): 1 \leq r_{1,j} \leq r_{2,j} \leq N, 1 \leq c_{1,j} \leq c_{2,j} \leq N
- 所有输入值均为整数
输入
N A B
r_{1,1} c_{1,1} r_{2,1} c_{2,1}
r_{1,2} c_{1,2} r_{2,2} c_{2,2}
:
r_{1,A} c_{1,A} r_{2,A} c_{2,A}
r'_{1,1} c'_{1,1} r'_{2,1} c'_{2,1}
r'_{1,2} c'_{1,2} r'_{2,2} c'_{2,2}
:
r'_{1,B} c'_{1,B} r'_{2,B} c'_{2,B}
- 第一行包含电路板尺寸 N,高桥的广告数量 A,以及青木的广告数量 B,用空格分隔。
- 以下 A 行每行描述高桥的一则广告。
- 的 i-第广告(1 \leq i \leq A) 给出为四个空格分隔的整数,表示左上角的单元格 (r_{1,i}, c_{1,i}) 和右下角的单元格 (r_{2,i}, c_{2,i}).
- 以下 B 行每行描述 Aoki 的一则广告。
- 的 j-第广告(1 \leq j \leq B) 给出为四个空格分隔的整数,表示左上角的单元格 (r'_{1,j}, c'_{1,j}) 和右下角的单元格 (r'_{2,j}, c'_{2,j}).
输出
在一行上输出高桥的广告和青木的广告重叠的单元格数。
示例输入 1
5 1 1 1 1 3 3 2 2 4 4
示例输出 1
4
示例输入 2
10 2 2 1 1 5 5 3 7 6 10 4 3 8 6 2 8 5 10
示例输出 2
15
示例输入 3
100 3 2 1 1 50 50 40 60 80 100 70 1 100 40 30 30 60 70 80 10 100 50
示例输出 3
1323