P9514 [JOI Open 2023] Garden / Garden

**Translated from [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)”.**

The JOI Kingdom is a mysterious kingdom with a vast territory. King JOI is the king of the JOI Kingdom, and he is planning to split off part of the territory to build his garden. The JOI network can be regarded as a sufficiently large 2D grid, tiled by square cells from top to bottom and from left to right. One cell is the origin. Let $(x,y)$ denote the cell reached by moving $x$ cells to the right from the origin, and then moving $y$ cells up. Here, moving $a$ cells to the left means moving $-a$ cells to the right. Similarly, moving $a$ cells downward means moving $-a$ cells upward. There are some artworks in the territory. These artworks are divided into **Type A** and **Type B** according to how they are placed in the territory. - There are $N$ kinds of Type A artworks. The $i$-th kind of artwork ($1\le i\le N$) is placed in every cell of the form $(P_i+kD,Q_i+lD)$, where $k,l$ are integers. - There are $M$ kinds of Type B artworks. The $j$-th kind of artwork ($1\le j\le M$) is placed in every cell of the form $(R_j+kD,y)$ (where $k,y$ are integers) or $(x,S_j+lD)$ (where $l,x$ are integers). Note that a single cell may contain multiple artworks of different kinds. King JOI plans to choose a rectangular region on the grid to build the garden. In other words, he chooses four integers $a,b,c,d$. Then the cells $(x,y)$ form King JOI’s garden, where $x,y$ are integers satisfying $a\le x\le b,c\le y\le d$. Since King JOI likes to see many kinds of artworks, for each of the $N+M$ kinds of artworks, the garden must contain at least one artwork of that kind. On the other hand, if the garden is too large, the citizens of the JOI Kingdom will get angry. Therefore, King JOI wants to minimize the number of cells contained in the garden while satisfying the above condition. Given the information about the artworks, write a program to compute the minimum number of cells contained in King JOI’s garden.

The first line contains three integers $N,M,D$. The next $N$ lines each contain two integers $P_i,Q_i$. The next $M$ lines each contain two integers $R_j,S_j$.

Output one integer in a single line, representing the minimum number of cells contained in King JOI’s garden.

**[Sample Explanation #1]** The figure below shows the cells $(x,y)$ in the JOI Kingdom’s territory satisfying $0\le x