题目描述

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

JOI 王国的疆域可视为一个充分大的二维网格，网格由正方形单元格密铺而成。坐标原点为某个单元格，$(x,y)$ 表示从原点向右移动 $x$ 个单元格、再向上移动 $y$ 个单元格所到达的单元格。其中，向左移动 $a$ 个单元格等价于向右移动 $-a$ 个单元格，向下移动 $a$ 个单元格等价于向上移动 $-a$ 个单元格。

领土内有 A、B 两类艺术品，具体分布如下：

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

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

JOI 君计划选择一个矩形区域建造花园，该区域由四个整数 $a,b,c,d$ 定义，包含所有满足 $a\le x\le b$、$c\le y\le d$ 的整数坐标单元格 $(x,y)$。花园需满足两个条件：

• 覆盖所有艺术品：对于 $N+M$ 种艺术品中的每一种，花园内至少包含该类艺术品的一个单元格。
• 面积最小化：花园包含的单元格数量（即 $(b-a+1)\times(d-c+1)$）需尽可能小。

给定艺术品信息，需计算满足条件的花园的最小单元格数量。

输入格式

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

接下来 $N$ 行，每行包含两个整数 $P_i,Q_i$，描述第 $i$ 种 A 类艺术品的参数。

接下来 $M$ 行，每行包含两个整数 $R_j,S_j$，描述第 $j$ 种 B 类艺术品的参数。

输出格式

输出一行一个整数，表示满足条件的花园的最小单元格数量。

样例 1

输入

$2$ $1$ $5$ $1$ $4$ $2$ $2$ $0$ $0$

输出

$8$ 下图展示了 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

输入

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

输出

$2840$

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

样例 3

输入

$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,5,6$ 的限制。

数据范围与提示

对于所有数据，满足：

• $N,M\ge 1$
• $N+M\le 5\times 10^5$
• $1\le D\le 5000$
• $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$