P9514 [JOI Open 2023] 花园 / Garden

**译自 [JOI Open 2023](https://contests.ioi-jp.org/open-2023/index.html) T3 「[庭園](https://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2023/garden/2023-open-garden-statement.pdf) / [Garden](https://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2023/garden/2023-open-garden-statement-en.pdf)」**

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 君的花园所包含的最小单元格数。

**【样例解释 #1】** 下图展示了 JOI 国领土中的满足 $0\le x