Background

Translated from JOI Open 2023 T3 “庭園 / Garden”.

Problem Description

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.

Input Format

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 Format

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

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

Hint

[Sample Explanation #1]

The figure below shows the cells $(x,y)$ in the JOI Kingdom’s territory satisfying $0\le x<10,0\le y<10$.

In the figure, circles and diamonds represent Type A and Type B artworks, respectively. The integer inside each circle or diamond indicates the kind index of the artwork. If King JOI chooses $a=1,b=2,c=2,d=5$, then King JOI’s garden is the black rectangular region. In this case, for these three kinds of artworks, King JOI’s garden contains at least one of each kind. The number of cells in the garden is $8$. Since there is no smaller garden that satisfies the condition, output $8$.

This sample satisfies the constraints of all subtasks.

[Sample Explanation #2]

This sample satisfies the constraints of subtasks $1,4,5,6$.

[Sample Explanation #3]

This sample satisfies the constraints of subtasks $1,5,6$.

[Constraints]

For all testdata, it holds that:

• $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$

The additional constraints and scores for the subtasks are shown in the table below.

Translated by ChatGPT 5