题目背景

译自 JOI Open 2023 T3 「庭園 / Garden」

题目描述

JOI 王国是一个神秘的王国，疆域辽阔无边。JOI 君是 JOI 国国王，他在计划分割疆域的一部分来建造他的花园。

JOI 网络可以考虑成一个充分大的二维网格，网格由从上到下和从左到右的正方形单元格密铺而成。有一个单元格是坐标原点。令 $(x,y)$ 表示表示从原点向右移动 $x$ 个单元格，再向上移动 $y$ 个单元格所到达的单元格。这里，向左移动 $a$ 个单元格意味着向右移动 $-a$ 个单元格。类似地，向下移动 $a$ 个单元格意味着向上移动 $-a$ 个单元格。

在领土内有一些艺术品。这些艺术品根据放置在领土上的方式分为 A 类和 B 类。

• 有 $N$ 种 A 类艺术品。第 $i$ 种艺术品（$1\le i\le N$）放在每个形如 $(P_i+kD,Q_i+lD)$ 的单元格上，其中 $k,l$ 为整数。
• 有 $M$ 种 B 类艺术品。第 $j$ 种艺术品（$1\le j\le M$）放在每个形如 $(R_j+kD,y)$（其中 $k,y$ 为整数）或 $(x,S_j+lD)$（其中 $l,x$ 为整数）的单元格上。

注意一个单元格中可能包含多种不同类别的艺术品。

JOI 君计划在网格中选择一个矩形区域建造花园。换句话说，他会选择四个整数 $a,b,c,d$。然后形如 $(x,y)$ 的单元格将构成 JOI 君的花园，其中 $x,y$ 是满足 $a\le x\le b,c\le y\le d$ 的整数。因为 JOI 君喜欢看到多种艺术品，对于任意 $N+M$ 种艺术品中的一种，JOI 君的花园中需要至少包含这种艺术品中的一个。另一方面，如果 JOI 君计划要建的花园过大，JOI 国的居民就会生气。因此，JOI 君希望最小化花园包含的单元格数使得满足上述条件。

给定艺术品的信息，写一个程序计算 JOI 君的花园所包含的最小单元格数。

输入格式

第一行三个整数 $N,M,D$。

接下来 $N$ 行，每行两个整数 $P_i,Q_i$。

接下来 $M$ 行，每行两个整数 $R_j,S_j$。

输出格式

输出一行一个整数，表示 JOI 君的花园所包含的最小单元格数。

2 1 5
1 4
2 2
0 0

8

3 4 100
20 26
81 56
20 3
58 71
74 82
95 61
95 61

2840

5 7 5000
1046 365
4122 1166
4009 2896
1815 4065
4372 1651
2382 123
1475 836
3313 4005
2579 568
4300 4867
1050 3214
3589 4653

10543092

提示

【样例解释 #1】

下图展示了 JOI 国领土中的满足 $0\le x<10,0\le y<10$ 的单元格 $(x,y)$。

在本图中，圆形和菱形分别表示 A 类和 B 类艺术品。圆形或菱形中的整数表示艺术品的种数。如果 JOI 君选择 $a=1,b=2,c=2,d=5$，JOI 君的花园就是黑色矩形区域。这种情况下，对于这三种艺术品，JOI 君的花园中至少会有每种中的一个。花园所占单元格数为 $8$。因为没有比这个花园占地更小且满足条件的花园了，因此输出 $8$。

这组样例满足所有子任务的限制。

【样例解释 #2】

这组样例满足子任务 $1,4,5,6$ 的限制。

【样例解释 #3】

这组样例满足子任务 $1,5,6$ 的限制。

【数据范围】

对于所有数据，满足：

• $N,M\ge 1$
• $N+M\le 5\times 10^5$
• $1\le D\le 5\ 000$
• $0\le P_i,Q_i,R_j,S_j<D$

详细子任务附加限制及分值如下表所示。

子任务	附加限制	分值
$1$	$M\le 8$	$15$
$2$	$D\le 10,N+M\le 5000$	$6$
$3$	$D\le 50,N+M\le 5000$	$8$
$4$	$D\le 100,N+M\le 5000$	$16$
$5$	$N+M\le 5000$	$30$
$6$	无附加限制	$25$